二分搜尋法 (Binary Search)

【用途】搜尋某個數字在陣列的哪個位置。
【概念】經過排序的陣列，若中間項比要搜尋的數字大，代表要搜尋的數字一定在前半段，因此把範圍縮小至前半段，以此類推。
【時間複雜度】O(log n)，例如 n = 8 時，最糟情況的步驟數為 log8 = log2³ = 3。

while(l<=r){
    int m = (l+r)/2;
    if(arr[m]==n) return m;
    else if(arr[m]>n) r=m-1;
    else l=m+1;
}
return -1;

#include <bits/stdc++.h>
using namespace std;
#define size 8
int arr[size] = {3,2,1,5,4,8,7,6};
int l=0, r=size-1;
int binarySearch(int n){
    while(l<=r){
        int m = (l+r)/2;
        cout<<"l="<<l<<", m="<<m<<", r="<<r<<'\n';
        if(arr[m]==n) return m; //找到了
        else if(arr[m]>n) r=m-1; //縮小至前半段
        else l=m+1; //縮小至後半段
    }
    return -1; //找不到
}
int main(){
    sort(arr, arr+size); //排序
    for(int i=0; i<size; i++) cout<<"arr["<<i<<"] = "<<arr[i]<<'\n';
    cout << binarySearch(5) << '\n';
}

arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5
arr[5] = 6
arr[6] = 7
arr[7] = 8
l=0, m=3, r=7
l=4, m=5, r=7
l=4, m=4, r=4
4