- 概念
要掌握二分法查找，首先我们要明白二分法查找是怎么运作的，为什么要用二分法查找。
- 这里有一个数组，共有十个元素，我们想找到其中一个元素，按照传统遍历的办法，我们写一个循环那么最多要循环十次，但是如果我们用二分法查找的话最多只用4次循环就可以做到。
传统办法代码示例：
int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };//定义数组 int n = 0; scanf("%d", &n);//输入要查找的数字 for (int i = 0; i < 10; i++)//从头到尾遍历查找 { if (arr[i] == n) { printf("找到了，位置在下标%d", i); break; } }
二分法查找讲解
二分法查找的精髓就是如果没查询到，下次将数据折半再进行查找，大大提高效率,，那么如果想砍掉一半数据，最重要的就是找到中间的数字，比如下图，我们想找的是2，那么我们先拿到中间数字5与2进行比较，5比2大，所以要找的肯定不是5右面的数（因为是有序数组），所以将5右面的数包括5一起pass掉
接下来我们继续在下标0-3的数字上进行查找中间数字为2，查找成功。
- 对于定位中间数，我们可以采用 最大的下标+最小的下标/2
于是便有了二分法查找必不可少的三个变量
left始化为0，因为最小的下标肯定是0
right ，sizeof(arr) / sizeof(arr[0]) - 1
mid ，(left + right) / 2，其中left和right的存在都是为了找出mid
- 有了这三个变量，问题就变得简单了，只要每次折半后修改left或者right的位置，然后产生新的mid，二分法查找就写好了
#include <stdio.h> int main() { int arr[10] = { 11,22,33,44,55,66,77,88,99,101 };//定义要查找的数组 int sz = sizeof(arr) / sizeof(arr[0]);//数组大小 int left = 0; //关键变量left用于定位范围左边 int right = sz - 1;//关键变量right用于定位范围右面 int mid = left + (right - left) / 2;//关键变量mid用于定位范围中间 int input = 0; int flag = 0;//标记循环结束后是否找到数字 scanf("%d", &input);//输入要查找的数字 while (left <= right) { if (input > arr[mid])//如果要查找的数字大于中间数，砍掉左半边 { left = mid + 1;//将左范围更正到原mid右一位 mid = left + (right - left) / 2;//将范围中间数更新 } else if(input <arr[mid])//如果要查找的书数字小于中间数，砍掉右半边 { right = mid - 1;//更新右范围为原mid左一位 mid = left + (right - left) / 2;//将范围中间数更新 } else//如果既不大于也不小于，则为等于，找到数字 { flag = 1;//将标记改为1 printf("找到了坐标为%d",mid); break;//跳出程序 } } if (flag == 0)//如果标记在循环中没有被修改，则证明没找到 { printf("没找到"); } }
总结
二分法查找其实很简单，主要就是找到中间数，每次进行折半即可。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3EXSYx5O-1677661166102)(https://img-home.csdnimg.cn/images/20220524100510.png =60x60)]
