【用途】搜尋某個數字在陣列中的位置。
【概念】經過排序的陣列，若中間項比要搜尋的數字大，代表要搜尋的數字一定在前半段，因此把範圍縮小至前半段，以此類推。
【時間複雜度】O(log n)。
#include <iostream>
#include <algorithm>
using namespace std;
int n = 8;
int a[8] = {3, 2, 1, 5, 4, 8, 7, 6};
int binarySearch(int x){
int l = 0, r = n - 1;
while(l <= r){
int m = (l + r) / 2;
if (a[m] == x) return m;
else if (a[m] > x) r = m - 1; // 縮小至前半段
else l = m + 1; // 縮小至後半段
}
return -1; // 找不到
}
int main(){
sort(a, a+n);
// 1, 2, 3, 4, 5, 6, 7, 8
cout << binarySearch(1);
}l = 0, m = 3, r = 7
l = 0, m = 1, r = 2
l = 0, m = 0, r = 0
ans = 0