c语言二分法查找数组中的数据 2021-10-29

C语言折半查找
题目：折半查找，在从小到大的数组中查找关键字key，找到其返回下标，失败则返回-1。
注意：一定要数组有序，否则没有这种算法，只可以从头到尾遍历。
代码：

#include<stdio.h>
#include<assert.h>
//折半查找（二分查找，一定数组有序）  时间复杂度O（logn）
int BinSearch(int arr[], int len, int key)
{
	assert(arr != NULL); //安全处理机制
	if (NULL == arr)
	{
		return -1;
	}

	int low = 0;   //左边指针
	int high = len - 1;  //右边指针
	int mid;//int mid = (low + high)/2; //每次缩小一半，需要和key比较的中间值

	while (low <= high)//当low和high之间范围内  至少有1个值，则继续比较
	{
		mid = (low + high) / 2;//mid = (high-low)/2 + low;//让mid指向临时的范围中间值

		if (arr[mid] == key)//如果mid指向的值就是key   则直接返回其下标
		{
			return mid;
		}
		else if (arr[mid] < key)  //如果mid指向的值小于key   则要找的key这个值一定在mid的右半边
		{
			low = mid + 1;
		}
		else//如果mid指向的值大于key   则要找的key这个值一定在mid的左半边
		{
			high = mid - 1;
		}
	}

	//此时while循环结束，还没有退出函数，则要找的这个值 一定不存在于这个数组内，则返回-1
	return -1;

}

int main()
{
	int arr[] = { 1,3,4,5,8,10,20,23,36,50 };
	int tmp = BinSearch(arr, sizeof(arr) / sizeof(arr[0]), 8);
	int main()
{
	int arr[] = { 1,3,4,5,8,10,20,23,36,50 };
	int tmp = BinSearch(arr, sizeof(arr) / sizeof(arr[0]), 10);
	//printf("所查找的数字在第%%d个。", tmp);
	if (tmp >=0)
	{
		printf("所查找的数字在第%%d个。", tmp);
	}
	else
	{
		printf("所查找数字不存在。");
	}
}
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

运行结果：
（1）当查找的数字为8时：

（2）当查找的数字为-1时：