​
​

活动地址：CSDN21天学习挑战赛
学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

查找的基本概念

在计算机科学中定义为：在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。也就是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。

查找算法的效率评价

平均查找长度ASL

查找成功的ASL：

查找失败的ASL：

查找分类

• 顺序查找
• 折半查找
• 索引查找
• B树/B+树
• 散列查找

折半查找

解释

在元素已经有序的前提下，每次用mid与指定元素比较，这样可以筛去一半元素加快查找速度。

代码实现（c语言）

# include
# include
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 8;
	int left = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int right = sz - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;//核心所在
		if (arr[mid] > k){
			right = mid - 1;
		}
 
		else if (arr[mid] < k){
		    left = mid + 1;
		}
 
		else{
			printf("找到了：%d\n", mid);
			break;
		}
    }
 
		if (left > right)//找不到
		{
			printf("找不到了\n");
		}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

解释：

1. int mid = (left + right) / 2;这句是折半查找的核心语句，作用就是计算两边元素之和除2（为中间元素）与要查找的元素做对比，进而确定查找数的范围。

​ 2. if (arr[mid] > k)表示情况一：求出的中间数若>要查找的数，就将右下标移位到mid的左边一位，之后再求出左下标与更新的右下标的中间元素，更新出新的范围，再与要找元素重新进行对比。

​ 3. else if (arr[mid] < k)表示情况二：求出的中间数若 <要查找的数，就将左下标移位到mid的右边一位，之后再求出左下标与更新的右下标的中间元素，更新出新的范围，再与要找元素重新进行对比。

​ 4. else表示情况三：若恰好相等，则直接跳出循环，printf打印输出。

​ 5. if (left > right)表示情况四：找不到。

折半查找评价

缺点:要有序顺序表（链表不合适呀）