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时:
推荐阅读