文章目录

• 一、什么是二分查找？
• 二、二分查找的具体例子

一、什么是二分查找？

二分查找的概念：当给到一组有顺序的数据时，需要查找一个数，是否在这组数据里面时，使用二分查找，通过这一组数据的两个数，确定一个范围，再根据这两个数，找到这个范围的中间值，使中间值与需要查找的那个数进行比较大小，若中间值需要查找的数，则表示查找的数在中间值的左边，中间值右边的数，可以全部舍弃。不断的进行上述操作，确定范围，找到中间值，与需要的数进行比较，不断的舍弃左边或者右边的数，大大提高效率。

可以类比于： A买了一双鞋，价格为300，让B猜价格。
第一种方法：从1到300，一个一个的猜（效率低）。
第二种方法：选取中间值：150，A说猜低了，则1-150的数就不用猜了，大大加快了效率，则在选取150-300的中间值：225，重复第一步的操作，直到成功的猜对价格。

现在我理解到，在计算机中写程序，只是为了解决我们生活中的问题，而为了能够成功的写出程序，就要理解计算机的思维，成功转化为计算机的语言，所以就需要锻炼我们的编程思维。

二、二分查找的具体例子

编写代码在一个整形有序数组中查找具体的某个数

首先，先用自己的话，讲述一遍流程：
通过元素的下标，找到中间元素，使中间元素和需要查找的值进行比较大小，若小于，说明需要查找的值，在右边，则舍弃左边，若大于，说明需要查找的值在左边，舍弃右边。
接着使用计算机语言描述：
1：通过元素的下标，找到中间元素

#includeint main(){int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };int sz = (sizeof(arr) / sizeof(arr[0]));int left = 0;int right = sz - 1;int mid = (left + right) / 2;return 0;}

2：使中间元素和需要查找的值进行比较大小，若小于，说明需要查找的值，在右边，则舍弃左边，若大于，说明需要查找的值在左边，舍弃右边。

#includeint main(){int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };int sz = (sizeof(arr) / sizeof(arr[0]));int left = 0;int right = sz - 1;int num = 7;int mid = (left + right) / 2;if (arr[mid] < num){// 舍弃中间值左边的数据，左边元素的下标需重新设置,//为何要加1，想象猜鞋子的价格，刚开始猜150，猜小了，//1-150，就舍弃了，从151到300中选平均值。150到151，就要去加1.left = mid + 1;}else if (arr[mid] > num){//舍弃中间值右边的数据，右边元素的下标需重新设置,//为何要减1，想上面猜鞋子的价格，如果刚开始猜150，猜大了，//150-300，就舍弃了，从1到149中选平均值。150->149，就要去减1.right = mid - 1;}else{printf("找到了，下标是:%d", mid);}return 0;}

3：然后我们现在去想，这只是一次检验，那检测失败之后呢，left或者right被修改了，又如何进行下一次检验呢，所以我们可以想到使用while循环或者for循环语句。

完整代码实现：

#includeint main(){int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };int sz = (sizeof(arr) / sizeof(arr[0]));int left = 0;int right = sz - 1;int num = 7;// 此时的while循环的条件是left<=right，为什么是这个？//我们想，使用二分查找的根本目的是什么？是查找一个数，// 所以这是使用while循环的目的，当数据还没有遍历完，就不能停止循环，//如何表明数据没有遍历完，左右两个下标是表示一个范围，有范围就代表有数据，如果范围不存在了，自然数据就遍历完了//范围存在时，左边元素的下标是小于等于右边元素的下标，左右两个下标相当时代表此时只剩一个值了。while (left <= right){int mid = (left + right) / 2;if (arr[mid] < num){// 舍弃中间值左边的数据，左边元素的下标需重新设置,//为何要加1，想象猜鞋子的价格，刚开始猜150，猜小了，//1-150，就舍弃了，从151到300中选平均值。150到151，就要去加1.left = mid + 1;}else if (arr[mid] > num){//舍弃中间值右边的数据，右边元素的下标需重新设置,//为何要减1，想上面猜鞋子的价格，如果刚开始猜150，猜大了，//150-300，就舍弃了，从1到149中选平均值。150->149，就要去减1.right = mid - 1;}else{printf("找到了，下标是:%d", mid);// 找到了之后，就退出while循环。break;}}if (left > right){printf("没有找到");}return 0;}