二分查找算法用于在一個有序的列表中查找某個值的位置，列表一般是升序排列的。循環比較中間值A[mid]和需要查找的值x，如果x小于等于中間值，那么在左邊找；如果x大于中間值，那么去右邊找。
二分查找的思想很簡單，但是有很多種寫法，我自己用的模板是仿照STL的二分函數，即有兩個版本，一個是查找第一個大于等于x的值的下標，若找不到則返回尾后指針；另一個版本是查找第一個大于x的值的下標，找不到返回尾后指針。

我的自用二分模板

#include <bits/stdc++.h> using namespace std;// 找出第一個大于等于x的元素的下標 int search_lower_bound(int *A, int left, int len, int x) {int mid, right = left + len;while (left < right) {mid = (left + right) / 2;if (x <= A[mid])right = mid;elseleft = mid + 1;}return left; }// 找出第一個大于x的元素的下標 int search_upper_bound(int *A, int left, int len, int x) {int mid, right = left + len;while (left < right) {mid = (left + right) / 2;if (x < A[mid])right = mid;elseleft = mid + 1;}return left; } const int LEN = 8; int A[LEN] = { 1, 1, 4, 5, 14, 19, 19, 810 }; //升序數組 int main() {for (int i = 0; i < LEN; i++) cout << A[i] << " "; cout << endl;int x;while (cin >> x) {int lo = search_lower_bound(A, 0, LEN, x);int up = search_upper_bound(A, 0, LEN, x);printf("A[%d] >= %d\n", lo, x);printf("A[%d] > %d\n", up, x);}return 0; }

兩個函數的唯一區別就是 if (x < A[mid])，如果帶等于號，則返回第一個大于等于x的值的下標；若不帶等于號，則返回第一個大于x的值的下標。

STL 二分函數
STL 二分查找函數更加靈活，它是模板函數，支持多種類型，包括自定義類型（需重載小于運算符），可以傳lambda表達式自定義比較規則。
下面附上兩個demo演示 STL 二分函數如何應用在自定義類型數組以及降序的整型數組。

降序數組demo

#include <bits/stdc++.h> using namespace std; int main() {int A[] = {10,8,6,4,2}; // 降序數組size_t x1 = lower_bound(A, A+5, 3, [](int a, int b) { return a > b; }) - A;size_t x2 = upper_bound(A, A+5, 3, [](int a, int b) { return a > b; }) - A;size_t x3 = lower_bound(A, A+5, 4, [](int a, int b) { return a > b; }) - A;size_t x4 = upper_bound(A, A+5, 4, [](int a, int b) { return a > b; }) - A;cout << x1 << endl; // 第一個小于等于3的元素下標cout << x2 << endl; // 第一個小于3的元素下標cout << x3 << endl; // 第一個小于等于4的元素下標cout << x4 << endl; // 第一個小于4的元素下標return 0; }

自定義類型demo

#include <bits/stdc++.h> using namespace std; struct MyPair {int a,b;MyPair(int _a, int _b) : a(_a), b(_b) {}bool operator<(const MyPair &other) {if (a != other.a) return a < other.a;return b < other.b;} }; int main() {vector<MyPair> v{{1,2}, {3,4}, {5,6}};int x = lower_bound(v.begin(), v.end(), MyPair(3,4)) - v.begin();cout << x << endl;return 0; }

總結

以上是生活随笔為你收集整理的二分查找自用模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。