vlambda博客
学习文章列表

二分查找

我一直 都认为 算法 很简单  当然包括二分查找也很简单，但事实真的如此吗？二分查找真的很简单吗？其实并不简单。看看 Knuth 大佬（发明 KMP 算法的那位）怎么说的：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...

这句话可以这样理解：思路很简单，细节是魔鬼。

其实我们在看一个算法题的时候记起来很简单，真正使用的时候却不是这么简单的。

最起码使用场景和具体需求理解起来还是比较吃力的。


简介

基本思想：又叫折半查找，要求待查找的序列有序，是一种快速查找算法，时间复杂度为 O(logn)，要求数据集为一个有序数据集。

使用

应用场景：一般用于查找数组元素，并且数组在查找之前必须已经排好序（一般是升序）。

最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。

步骤：

1、取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，

2、如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。

3、直到查找到了为止，否则序列中没有待查的关键字。

代码示例：

这个场景是最简单的，可能也是大家最熟悉的，即搜索一个数，如果存在，返回其索引，否则返回 -1。

public static int biSearch(int []array,int a){
    int lo=0;//左
    int hi=array.length-1; //右
    int mid;
    while(lo<=hi){
        mid=(lo+hi)/2;//中间位置
        if(array[mid]==a){
            return mid+1;
        }else if(array[mid]<a){ //向右查找
            lo=mid+1;
        }else{ //向左查找
            hi=mid-1;
        } 
  }
    return -1;
}

这里会有一个疑问：为什么 while 循环的条件中是 <=，而不是 < ？

因为初始化 right 的赋值是 array.length-1，即最后一个元素的索引，而不是 array.length。

这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 array.length 是越界的。

我们这个算法中使用的是 [left, right] 两端都闭的区间。这个区间就是每次进行搜索的区间，称为「搜索区间」(search space)。

最后总结

因为我们初始化 right = array.length-1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while ((lo<=hi)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 array[mid] == target 时可以立即返回