数组算法--二分查找
目录
一.前言
二分查找也叫折中查找，为什么会这样叫呢？就是因为我们二分查找的核心逻辑就是每查找完一次，都能将查找的范围给缩小一半，也就是折中。但使用二分查找又有个很大的前提，那就是该数组里的元素得是有序排序的，也就是从小到大排序或者从大到小排序。
二.算法的核心思路
首先我们以一个从小到大进行排序的数组{3,4,5,6,7,8}为例，二分算法之所以能够每次将范围缩小一半就是因为它设置了中间值，我们把它命名为mid。
接着我们明确下我们要查找的范围，也就是设置一个最左边的值，设为min，它的值会是索引号0。设置一个最右边的值为max，它的值就会是数组长度减一。而我们的mid值就是对这两者进行求和再除以2的结果。
在这个例子中，我们的min=0，max=6-1=5,mid=(0+5)/2=2。它们值也就是索引值。
接着我们只需要拿数组中索引值为mid的数据来和我们要查找的数据进行大小对比即可。要是数据大于mid的数据，且我们这里是按照从小到大进行排序的，所以我们就能确定我们要查找的数据在我们的mid和max中间。
这个时候我们就可以缩小范围，让min等于mid的值加一，max保持不变，mid还是min和max两者求和后的一半。
同理，要是小于mid的数据，就让min保持不变，max的值等于mid减一。达到一个每查找一次就能将范围缩小一半的效果，同时，因为mid已经和要查找的数据进行对比过了，所以我们每次更改min和max的值时候，就需要加一或者减一。
三.算法的核心代码以注释详解
#include<stdio.h>
int binaryFind(int arr[], int len, int num);
int main() {
//给定一个有序的数组和要查找的数，对它进行二分查找。
int arr[] = {11,22,33,44,55,66,77};
int len = sizeof(arr) / sizeof(int);
//定义一个num变量用来存放要查找的数据
int num = 66;
//定义一个变量来接收函数传递过来的索引
int index = binaryFind(arr, len, num);
printf("%d\n", index);
return 0;
}
int binaryFind(int arr[], int len,int num) {//别忘了声明函数
//设置min和max的初始值
int min = 0;
int max = len - 1;
//我们查找结束的条件就是当min>max的时候，这表示查完数组中所有的元素都没有满足的。
while (min <= max) {
//每次比较完更新mid的值
int mid = (min + max) / 2;
//判断完之后来决定范围的更新。
if (arr[mid] < num) { //表示要查找的数据在mid的右边，如果是从大到小排序的，则是在左边。
min = mid + 1;
}
else if (arr[mid] > num) {//在mid的左边，更新max的值来缩小范围。
max = mid - 1;
}
//这种情况是刚好mid索引处的值等于要查找的数据
else {
return mid;
}
}
return -1;
}下面我们来看下运行的结果：
这里的5表示我们要查找的数据在数组中的索引值为5的地方。
原文地址：https://blog.csdn.net/2303_78660417/article/details/140568420
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！