【21天算法学习】折半查找

作者简介：
🍀姓姜，字君竹。
🍁浅薄观点：科以载文，文以载道
🌱软件技术升计科，计划考研
🌾要有最朴素的生活和最遥远的梦想，即使明日，天寒地冻，路遥马亡​​​

1. 概念及介绍
     折半查找（搜索），也称二分查找（搜索）、对数搜索，是一种在有序数组中查找某一特定元素的搜索算法。
     搜索从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索结束。如果要查找的元素大于或者小于之中间元素，则在数组大于或小于中间元素的那一半中查找，且也是从这一半的中间元素开始比较。然后一直重复上述流程，直到找的要找的元素，或者找完不能再折半查找为止。这种搜索算法每一次比较都使得搜索范围缩小了一半。
     折半查找查找速度快、次数少、平均性能好，但查找对象必须是有序的，且很难实现插入删除。所以折半查找使用不常变动且需要频繁查找的有序列表。

2. 时间空间复杂度
     时间复杂度与寻找次数相关，如果要寻找的值第一次就找到了，则此时的时间复杂度为常数级O(1)。折半查找每查找一次，搜索空间就会折半，所以折半查找正常的时间复杂度是一个以2位底，相对于n的对数O(log₂n)。
     折半算法并没有改变原有的元素集合，只需要几个变量记录相关信息，所以空间复杂度为常量级O(1)。

3. 图解
   

4. 代码实现

int main() {
	int a[] = { 0, 12, 23, 24, 25, 34, 45, 56, 67, 68, 78, 89, 90 };
	int key = 24;
	int left = 0;
	int right = sizeof(a) / sizeof(a[0]) - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (a[mid] == key) {
			printf("下标是%d", mid);
			return 0;
		}
		else if (a[mid] < key)
			left = mid + 1;
		else if (a[mid] > mid)
			right = mid - 1;
	}
	if (left > right) {
		printf("没找到");
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。