C/C++ 二元搜尋法 Binary Search

本篇 ShengYu 介紹 C/C++ 二元搜尋法 Binary Search。

C/C++ Binary Search 二元搜尋法(迴圈版本)

這篇介紹 C/C++ Binary Search 二元搜尋法迴圈的版本，遞迴的版本下一節會介紹到，要使用二元搜尋法前有個前提，就是必須要確認資料是已排序過的，如果資料未排序可以用 sort 來先排序，接著使用迴圈每次將 key 值與中間值作比較，如果 key 值大於中間值的話，下次就往右側搜尋，右側為值較大的一邊，否則就往左側搜尋，左側為值較小的一邊，這的動作一直持續到比對到符合的 key 值或者迴圈結束未找到 key 值，範例如下，

// g++ cpp-binary-search.cpp -o a.out -std=c++11
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int binary_search(const vector<int> &data, int key) {
    int low = 0;
    int high = data.size()-1;
    while (low <= high) {
        int mid = int((low + high) / 2);
        if (key == data[mid])
            return mid;
        else if (key > data[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> data = {1, 9, 2, 7, 4, 10, 3, 8, 5, 6};
    int key = 7;
    
    sort(data.begin(), data.end());
    
    for (auto &i : data)
        cout << i << " ";
    cout << "\n";

    int ret = binary_search(data, key);
    if (ret == -1)
        cout << "找不到\n";
    else
        cout << "找到索引值" << ret << "\n";
}

輸出結果如下，

1 2 3 4 5 6 7 8 9 10 
找到索引值6

C/C++ Binary Search 二元搜尋法(遞迴版本)

剛剛介紹的二元搜尋法是迴圈的版本，這邊要介紹二元搜尋法遞迴版本，遞迴的版本要稍微修改一下，思考方式也要稍微轉換一下，

// g++ cpp-binary-search2.cpp -o a.out -std=c++11
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int binary_search(const vector<int> &data, int low, int high, int key) {
    if (low > high) {
        return -1;
    }
    
    int mid = int((low + high) / 2);
    if (key == data[mid])
        return mid;
    else if (key > data[mid]) {
        low = mid + 1;
        return binary_search(data, low, high, key);
    } else {
        high = mid - 1;
        return binary_search(data, low, high, key);
    }
}

int main() {
    vector<int> data = {1, 9, 2, 7, 4, 10, 3, 8, 5, 6};
    int key = 7;
    
    sort(data.begin(), data.end());
    
    for (auto &i : data)
        cout << i << " ";
    cout << "\n";

    int ret = binary_search(data, 0, data.size()-1, key);
    if (ret == -1)
        cout << "找不到\n";
    else
        cout << "找到索引值" << ret << "\n";
}

輸出結果如下，

1 2 3 4 5 6 7 8 9 10 
找到索引值6

其它相關文章推薦
如果你想學習 C++ 相關技術，可以參考看看下面的文章，
C/C++ 循序搜尋法 Sequential Search
C/C++ 新手入門教學懶人包