漫画:什么是二分查找?(修订版)

小灰 梦见 2019-05-29

本次修正了周一发布漫画中所存在的两个小问题:


1.猜数字游戏中,大黄报出“175”,小灰应该回答“大了”,而不是“小了”。

2.代码中,获取中位数下标的逻辑不能写成 mid=(start+end)/2这样写的话,如果start和end值很大,有可能出现溢出。最严谨的写法是:mid=start+(end-start)/2。


非常感谢大家的指正!





—————  第二天  —————





什么意思呢?我们来举两个栗子:


给定一个有序数组 

2,5,7,9,12,14,20,26,30


Case 1:


Case 2:







————————————









为什么说这样效率最高呢?因为每一次选择数字,无论偏大还是偏小,都可以让剩下的选择范围缩小一半。


给定范围0到1000的整数:




第一次我们选择500,发现偏大了,那么下一次的选择范围,就变成了1到499:



第二次我们选择250,发现还是偏大了,那么下一次的选择范围,就变成了1到249:



第三次我们选择125,发现偏小了,那么下一次的选择范围,就变成了126到249:



以此类推,最坏的情况需要猜测多少次呢?答案是 log1000 = 10次,也就是让原本的区间范围进行10次 “折半”。



刚才我们所分析的是猜数字的游戏。如果我们把场景转换成最初的面试问题:在包含1000个整型元素的有序数组中查找某个特定整数,又该如何去做呢?


同样道理,我们可以首先判断下标是499的元素(因为数组下标从0开始,到999结束),如果元素大于要查找的整数,我们再去判断下标是249的元素,然后判断下标124的元素......以此类推,直到最终找到想要的元素,或者选择范围等于0为止。


上述这个过程,就是所谓的二分查找算法,查找的时间复杂度是log(n)




  1. public static int binarySearch(int []array,int target){

  2. //查找范围起点

  3. int start=0;

  4. //查找范围终点

  5. int end=array.length-1;

  6. //查找范围中位数

  7. int mid;

  8. while(start<=end){

  9. //mid=(start+end)/2 有可能溢出

  10. mid=start+(end-start)/2;

  11. if(array[mid]==target){

  12. return mid;

  13. }else if(array[mid]

  14. start=mid+1;

  15. }else{

  16. end=mid-1;

  17. }

  18. }

  19. return -1;

  20. }


  21. public static void main(String[] args) {

  22. int[] array = new int[1000];

  23. for(int i=0; i<1000;i++){

  24. array[i] = i;

  25. }

  26. System.out.println(binarySearch(array, 173));

  27. }








—————END—————



最后安利一下小灰创建的免费知识星球

每天都有许多有趣的抢答活动和各种奖品,

关键是不要钱!欢迎大家扫码加入:


    已同步到看一看

    发送中

    本站仅按申请收录文章,版权归原作者所有
    如若侵权,请联系本站删除
    觉得不错,分享给更多人看到
    梦见 热门文章:

    漫画:编程其实是文科    阅读/点赞 : 1108/17

    我是一个线程    阅读/点赞 : 693/22

    漫画:三分钟了解敏捷开发    阅读/点赞 : 644/17

    漫画:什么是中间人攻击    阅读/点赞 : 613/16

    我是一个Java class    阅读/点赞 : 552/10

    网贷遇雷潮,投资者如何避雷?    阅读/点赞 : 0/0