【用途】搜尋某個數字在陣列的哪個位置。
【概念】經過排序的陣列,若中間項比要搜尋的數字大,代表要搜尋的數字一定在前半段,因此把範圍縮小至前半段,以此類推。
【時間複雜度】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