物联网
您现在所在的位置:首页>企业动态>物联网

常见查找算法之二分查找

编辑:学到牛牛IT培训    发布日期: 2022-01-05 14:32:23  

二分查找是指在有序数组中查找某一元素,前提一定是在有序的数组。二分查找也叫折半查找法,就是将数组分成两半,不断地缩小范围查找。

首先我们要有一个有序的数组,如图1所示

二分查找算法图1.png

图 1

分别找出中间值和左右两边开始查找的位置。如图2所示

二分查找算法图2.png

图 2

找到中间值的目的就是为了方便拿中间值和要查找的目标值作比较,当目标值和中间值相等时,就表示在此数组中找到了目标值,但如果中间值和目标值不相等时怎么办呢?因为数组中的元素个数不止一个,所以目标值和中间值的对比肯定是不止一次的,此时就需要循环遍历数组,循环地拿目标值和中间值作比较。可是如果每次的中间值都是同一个值就没有什么比较可言了,所以随着数组的循环,每一次的中间值都是不一样的。那中间值是如何变化的呢?

假如待查找的值为num。

二分查找算法图3.png

图 3

将目标值和中间值比较,目标值比中间值小,查找范围就应缩小为最左边至目前的中间值减一的位置,那么下一次查找时,左右两边开始查找的位置如图4所示 

二分查找算法图4.png

图 4

移动查找范围后,找出新的中间值,拿目标查找值和新的中间值作比较,这一次目标值和中间值相等,则表示查找成功,此数组中有此目标值存在。

具体代码如下:

int binarySearch ( int *arr, int left, int right, int goal)
{
while(left <= right)    //必须满足左边小于或等于右边才能进入循环
{
int mid = (left + right)/2;  //每查找一次就更新一次中间值
if(goal < arr[mid])
{
right = mid - 1;
}
else if(goal > arr[mid])
{
left = mid + 1;
}
else
{
return mid;  //查找到后结束程序
}
}
return -1;
}

如果数组中没有此数,那程序是如何运行的呢?

还是这个有序的数组

二分查找算法图5.png

图 5

还是那个查找范围

二分查找算法图6.png

图 6

这一次的目标值Num为10。

二分查找算法图7.png

图 7

目标值比中间值大,这次改变的查找范围就应该把最左边开始查找的位置移动到当前中间值的位置,如下图

二分查找算法图8.png

图 8

此时只需要不断的比较,不断的找出新的中间值和目标值做对比。

二分查找算法图9.png

图 9

在这个例子中目标值永远比中间值大,所以最后会查找失败,此数组中没有目标值。

二分查找还可以用递归的方式实现,以下代码就是具体的实现方法啦~

int binarySearch1(int *arr, int right, int left, int goal )
{
int mid = (right + left)/2;
if(goal == arr[mid])
{
      return arr[mid];
}
else if(goal > arr[mid])
{
return binarySearch1 (arr,right,left+1, goal);
     }
     else if(goal < arr[mid])
     {
          return binarySearch1 (arr,right-1,left, goal);        
     }
 }
免费试学
课程好不好,不如实地听一听

封闭学习

2

1

联系我们

电话:028-61775817

邮箱:1572396657@qq.com

地址:成都高新西区西芯大道4号

  • 学到牛牛在线咨询

    扫一扫,免费咨询

  • 学到牛牛公众号

    微信公众号

学一流技术,找高薪工作

7-24小时服务热线:

028-61775817

版权声明 网站地图

蜀ICP备2021001672号

课程问题轻松问