C++二分查找详解

一、介绍：

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

二、比较演示： 

 三、方法：

        （1）设置查找区间：

int left;// C++自动初始化为0
int right=n;

        （2）若查找区间不存在，则查找失败，返回；否则执行（3）。

        （3）取中间位，比较与 ，有三种情况：

                1. 若 x < a[mid]，则right = mid - 1；查找在左半区间进行，转（2）；

                2. 若 x > a[mid]，则left = mid + 1；查找在右半区间进行，转（2）；

                3. 若 x = a[mid]，则查找成功，返回mid的值；

 四、时间复杂度比较：

        （1）顺序查找：

                1.最好时间复杂度：

                        

                2.最坏时间复杂度：

                        

        （2）二分查找：

                1.最好时间复杂度：

                        

                2. 最坏时间复杂度：

                        

 五、代码部分：

#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;
}

如果这篇文章对你有帮助的话，记得点个赞和收藏再走啊 ！！！