二分查找详解

定义

二分查找又称折半查找，是一种相比较顺序查找效率较高的查找方法。但是，二分查找要求线性表中的记录必须采用顺序存储。

动画演示

查找方法

时间复杂度比较

（1）顺序查找： 1.最好时间复杂度： 2.最坏时间复杂度： （2）二分查找： 1.最好时间复杂度： 2. 最坏时间复杂度：

示例代码

参考1

#include<iostream>
using namespace std;
int n, x, a[105];
int bs(int left, int right, int x) {
	int mid = (left + right) / 2;
	if (x < a[mid]) {
		return bs(left, mid - 1, x);
	}
	else if (x > a[mid]) {
		return bs(mid + 1, right, x);
	}
	else {
		return mid;
	}
}
int main() {
	cin >> n >> x;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << bs(0, n, x);
	return 0;
}

参考2

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int a[N],b[N];
int n,m;
//二分查找 
void binarySearch(int k){
   int start=0;
   int end=m;
   while(start<=end){
       int mid=(start+end)/2;
       if(b[mid]==k){
           cout<<k<<" ";
           break;
       }
       else if(b[mid]<k) start=mid+1;
       else if(b[mid]>k) end=mid-1;
   }
} 
int main()
{
   cin>>n>>m;
   for(int i=0;i<n;i++) cin>>a[i]; 
   for(int i=0;i<m;i++) cin>>b[i]; 
   sort(b,b+m);
   for(int i=0;i<n;i++){
        binarySearch(a[i]);
     }
   return 0; 
}