漫画:什么是二分查找?

来自:程序员小灰(微信号:chengxuyuanxiaohui),作者:小灰





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





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


给定一个有序数组 

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]<target){

  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. }







来自:程序员小灰(微信号:chengxuyuanxiaohui),作者:小灰

程序员小灰

推荐↓↓↓
算法与数据结构
上一篇:LeetCode 上第 268 号问题:缺失数字 下一篇:如何理解二分查找?生活中还能用来设计骗局?