目录

​一、算法介绍

1.算法思想

2.算法流程

二、算法实现

1.代码实现

2.测试用例及结果

三、性能分析

1.时间复杂度

2.空间复杂度

1.算法思想

二分查找也称折半查找，是一种效率比较高的查找算法，但是运用前提是查找的序列已经有序。其核心思想就是利用序列有序的特点，每次对序列中间元素进行比较，判断其与待查找元素的大小关系，来确定待查找元素是否是当前元素，或是在当前元素的左半部分还是右半部分，从而每次比较都能够淘汰一半的元素，缩小查找区间，所以其拥有较高的查找效率。

2.算法流程

示例：给定序列{1，2，3，4，5，6，7，8，9}，查找元素3。

每次比较后，若没有查找到待查找元素，都需要根据比较结果改变查找区间一侧边界，然后更新mid的位置，再进行下一次查找。

二、算法实现

1.代码实现

#include
using namespace std;

//成功：返回下标  失败：返回-1
int BinarySearch(int* arr, int size, int key) {//二分查找  
	int left = 0;
	int right = size - 1;
	while (left <= right) {//注意等于时，也需要比较
		int mid = (left + right) / 2;
		if (arr[mid] < key) {
			left = mid + 1;
		}
		else if (arr[mid] > key) {
			right = mid - 1;
		}
		else {//查找成功
			return mid;
		}
	}
	return -1;//查找失败
}

void Test() {
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	int size = sizeof(arr) / sizeof(arr[0]);
	int key;
	cout << "请输入待查找元素：";
	cin >> key;

	int index = BinarySearch(arr, size, key);
	if (index == -1) {
		cout << endl << "没有待查找元素！" << endl;
	}
	else {
		cout << endl << "元素" << key << "所在位置下标为：" << index << endl;
	}
}

int main() {
	Test();
	return 0;
}

2.测试用例及结果

序列：1，2，3，4，5，6，7，8，9

查找元素3：

查找元素：9

 

查找元素：10

 

查找元素：0

 

三、性能分析

1.时间复杂度

最坏情况O()：

根据算法思想可知，最坏情况即最后一次比较才找到待查找元素，也即是left与right重叠，查找区间内只剩一个元素时。根据算法思想每次淘汰一半元素可知，就相当于每次查找区间内元素减少一半，减少几次后只剩1个元素即最大的查找次数，即次，所以最坏情况下的时间复杂度为

O()

 最好情况O(1)：

最好情况即只需要比较一次就找到待查找元素，根据算法思想可知此时待查找元素刚好位于序列的中间位置，所以最好情况下的时间复杂度为O(1)。

平均情况O()：

综合两种情况，二分查找的时间复杂度为O()。

2.空间复杂度

O(1)

由于算法中只设置了几个临时变量用于限定查找区间和查找元素，并没有借助额外的辅助空间，所以空间复杂度为O(1)。
​

活动地址：CSDN21天学习挑战赛