二分法查找整型有序数组中具体的某个数
程序员文章站
2022-03-13 18:20:53
...
二分法
在数组中寻找某个元素时,一般都是从头到尾进行遍历。
为了提高效率,可以采用二分法,每次和中间的值做对比,缩小查找区间。
解决思路
定义四个变量:left所查找区间的左边 right所查找区间的右边 mid所查找区间的中间值 和我们想要查找的数toFind
数学中我们可以这样表示:[left,right] mid=(left+right)/2
如果toFind<mid ,那么所查找的区间更新为[left,mid)
如果toFind>mid,那么所查找的区间更新为(mid,right]
直到toFind=mid,就找到了我们想要查找的数字
代码示例
这里自己定义了一个数组{ 1, 5, 7, 13, 24, 16 },如果需要键盘输入自行修改即可
#include<stdio.h>
#include<windows.h>
#pragma warning(disable:4996)
int main()
{
int toFind = 0;
int arr[] = { 1, 5, 7, 13, 24, 16 };
int left = 0;
printf("请输入要查找的数字:\n");
scanf("%d",&toFind);
int right = sizeof(arr) / sizeof(arr[0]) - 1;
while(left<=right){
int mid = (left + right) / 2;
if (toFind <arr[mid]){
right = mid - 1;
}
else if (toFind>arr[mid]){
left = mid + 1;
}
else{
printf("找到了,数组下标为:%d\n", mid);
break;
}
}
if (left > right){
printf("找不到!\n");
}
system("pause");
return 0;
}
运行结果
再吃一颗苹果~~加油鸭~~~
上一篇: C语言二分查找函数