二分查找是指在有序数组中查找某一元素,前提一定是在有序的数组。二分查找也叫折半查找法,就是将数组分成两半,不断地缩小范围查找。
首先我们要有一个有序的数组,如图1所示
图 1
分别找出中间值和左右两边开始查找的位置。如图2所示
图 2
找到中间值的目的就是为了方便拿中间值和要查找的目标值作比较,当目标值和中间值相等时,就表示在此数组中找到了目标值,但如果中间值和目标值不相等时怎么办呢?因为数组中的元素个数不止一个,所以目标值和中间值的对比肯定是不止一次的,此时就需要循环遍历数组,循环地拿目标值和中间值作比较。可是如果每次的中间值都是同一个值就没有什么比较可言了,所以随着数组的循环,每一次的中间值都是不一样的。那中间值是如何变化的呢?
假如待查找的值为num。
图 3
将目标值和中间值比较,目标值比中间值小,查找范围就应缩小为最左边至目前的中间值减一的位置,那么下一次查找时,左右两边开始查找的位置如图4所示
图 4
移动查找范围后,找出新的中间值,拿目标查找值和新的中间值作比较,这一次目标值和中间值相等,则表示查找成功,此数组中有此目标值存在。
具体代码如下:
#include <stdio.h>
int Binary (int arr[],int left,int right,int num )
{
while(left <= right) //必须满足左边小于或等于右边才能进入循环
{
int mid = (left + right)/2; //每查找一次就更新一次中间值
if(num < arr[mid])
{
right = mid - 1;
}
else if(num > arr[mid])
{
left = mid + 1;
}
else
{
printf("find "); //查找到后结束程序
return mid;
}
}
return -1;
}
如果数组中没有此数,那程序是如何运行的呢?
还是这个有序的数组
图 5
还是那个查找范围
图 6
这一次的目标值Num为10。
图 7
目标值比中间值大,这次改变的查找范围就应该把最左边开始查找的位置移动到当前中间值的位置,如下图
图 8
此时只需要不断的比较,不断的找出新的中间值和目标值做对比。
图 9
在这个例子中目标值永远比中间值大,所以最后会查找失败,此数组中没有目标值。
二分查找还可以用递归的方式实现,以下代码就是具体的实现方法啦~
#include <stdio.h>
int func(int arr[],int right, int left,int num)
{
int mid = (right + left)/2;
if(num == arr[mid])
{
return arr[mid];
}
if(num > arr[mid])
{
return func(arr,right,left+1,num);
}
if(num < arr[mid])
{
return func(arr,right-1,left,num);
}
}