iT邦幫忙

1

【小馬的資結演算法秘笈】(1)二分搜索法(Binary Search) #附c++程式教學

嗨嗨,大家好,我是心原一馬,
「資料結構」是資訊領域一個蠻重要的課題,
用意是如果我們能將資料整理的更有結構,
那麼使用上會更加方便,
比如說在一堆有排序過的物品中找東西,
一定比雜亂的垃圾堆中找東西容易。
所以這次要挑戰撰寫「資料結構的演算法」主題的系列文

閱讀此系列文的先備知識

  1. 大概知道時間複雜度(big O)的概念,以對於演算法的快慢大致有個感覺,可參考初學者學演算法|談什麼是演算法和時間複雜度這篇文章
  2. 程式部分選擇以c++實作,需要懂一些c++語法

簡介

二分搜尋(binary search)是一個蠻經典的演算法,
在資料有排序過的情形下,
可以用O(log n)的時間複雜度找到資料

首先,我們思考一個情境:
假設現在大學期末考剛考完,
你要去找你的助教領取考卷,
但是你的助教說他很忙,
考卷就放在隔壁的桌上,
請你自己去找,
那麼你該如何找到你的考卷呢?
(假設你的學號是107023456,考卷有200張)

線性搜尋(linear search)

https://ithelp.ithome.com.tw/upload/images/20200310/20117114YHWYTTPVta.png
最簡單的方法就是你一張張的把考卷拿起來看,
你最多把200張考卷都看完後,
你就能夠找到自己的考卷了

二分搜尋(binary search)- 僅適用在排序過的物件中尋找

你正想繼續檢查全部的考卷,
這時你的助教告訴你,
考卷的順序已經按照學號順序由小到大排過了,
那麼你有沒有更聰明的方式去找你的考卷呢?
(假設學號全部相異)

這時你就可以直接從中間的地方開始找,
比如說看第100張考卷好了,
假設第100張考卷上的學號是108021114
比你的學號大,那麼你的考卷一定是在前面100張裡面,
一下子你就可以少看一半的考卷了…

以此類推,每次都可以少搜索一半的數量,
可以大大的節省找東西的時間

程式實作

我們以c++的vector來儲存資料
我們欲實作的函數形式定義如下:

bool binarySearch(std::vector<int>& vec, int target);

意思是說給你一個排序過的vec,給你一個整數target
目標是查找target是否在這個vec裡面,
是的話回傳true,不是的話回傳false

首先,我們用vector的迭代器來查找位置

auto beg = vec.begin(), end = vec.end();
auto mid = vec.begin() + (end - beg) / 2;

vec.begin()指向vector的第一個元素,
vec.end()vector的最後一個元素的後面一格位置,
mid指的就是vec中間的元素,
以圖示來說像這樣:
https://ithelp.ithome.com.tw/upload/images/20200310/20117114glpfQtk855.png

假設這個vector總共就四個元素好了,
蠻多人可能會以為vec.end()指向從左往右數的第四個問號的位置,
實際上vec.end()應該指向第四個問號右邊一格的位置。
以此例來說,end - beg距離四格,
所以auto mid = vec.begin() + (end - beg) / 2;代表的位置是vec.begin()向右兩格

while迴圈的實作

再來,二分搜索法的精神就是不斷的去找陣列中間的位置,
直到找到目標,程式碼如下:

while (beg!= end) {
    if (target < *mid)
        end = mid;
    else if (target > * mid)
        beg = mid + 1;
    else
        return true;
    mid = beg + (end - beg) / 2;
}
return false;

變數begend的涵義是說,
我們想找的目標數字有可能在beg(包含)~end(不包含)的位置之間
我們去檢查mid裡面的數字,

  • 如果目標比中間數字小,表示目標數字不可能在右邊的範圍裡了,故重設end = mid

舉例來說,假設想找的目標數字是「2」,結果一打開發現中間的數字是「4」,
表示mid右邊的範圍都不可能是目標
https://ithelp.ithome.com.tw/upload/images/20200310/20117114wTr9xI8XNF.png

  • 如果目標比中間數字大,表示目標數字不可能在右邊的範圍裡了,故重設beg = mid+1
  • 如果目標剛好就在中間的數字裡,恭喜你找到了,回傳true即可

如此反覆下去,當begend的位置相同時,
表示所有可能的範圍都被刪光了,
回傳false表示想找的目標數字不在vector裡面

完整可測試的程式碼如下

#include <iostream>
#include <vector>
using namespace std;

bool binarySearch(std::vector<int>& vec, int target)
{
    auto beg = vec.begin(), end = vec.end();
    auto mid = vec.begin() + (end - beg) / 2;
    while (beg!= end) {
        if (target < *mid)
            end = mid;
        else if (target > * mid)
            beg = mid + 1;
        else
            return true;
        mid = beg + (end - beg) / 2;
    }
    return false;
}

int main()
{
    vector<int> v = {1,3,15,26,35,88,125};
    int value;
    while (std::cin >> value) {
        cout << (binarySearch(v, value) ? "找到元素" : "沒找到元素") << endl;
    }
    return 0;
}

嘿,二分搜索法必須用在有排序的資料上,
那如果一開始的資料很亂,該如何排序呢?
下一章我們將談談「排序」這個經典主題啦~


尚未有邦友留言

立即登入留言