>大家有没有玩过猜数字游戏,你猜一个数就说你猜大了还是猜小了,猜正确就结束,你是怎么猜呢?不会从头到末尾一个一个猜吧。我们先找中间的数猜一次缩减一半的范围。
在 1 2 3 4 5 6 7 8 9 10 查找7 和 17
1.把数据存放在数组中并且把7和17分两次需要输入的k值定义并且接受
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int k;
scanf("%d", &k);
2.找出数组两边的下标
1>计算数组长度
int sz = sizeof(arr) / sizeof(arr[0]);
2>
int left = 0;
int right = sz - 1;
3.在数组中查找是否有k
1>先找到中间的数字下标,若不能整除向下约分
int mid = (left + right) / 2;
2>用数组中间元素与要找的k进行比较
(1)若arr[mid]<k 则k在arr[mid]右侧,故arr[mid]及其左侧均不为k,查找范围左侧为mid+1
(2)若arr[mid]>k 则k在arr[mid]左侧,故arr[mid]及其右侧均不为k,查找范围右侧为mid-1
(3)若arr[mid]==k 则查找完成
3>没找到进行循环处理,若left<=right继续循环,否则终止循环
容易出现思考问题的是left == right
举个例子:当查找为k = 7时 第3次循环语句结束后mid = 5 left = 6 right = 6时还要进行下一次循环
前三次循环结束后mid left right 的值 1:4 5 9 2:7 5 6 3:5 6 6
下面的图示意了二分查找7的过程
![watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAcmVhbCBXYW5neWFuYmlu,size_20,color_FFFFFF,t_70,g_se,x_16](https://img-blog.csdnimg.cn/a3d09bd617904d8ea0177f934509aaff.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAcmVhbCBXYW5neWFuYmlu,size_20,color_FFFFFF,t_70,g_se,x_16)
#include<stdio.h>
#include<string.h>
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int k;
scanf("%d", &k);
int sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid] > k)
{
right = mid - 1;
}
else
{
printf("找到了,下标为:%d", mid);
break;
}
}
if (left > right)
{
printf("找不到!");
}
return 0;
}
对于找中间元素下标如果数字太大的话right+left就会太大溢出,可以改成mid=left+(right-left)/2