《数据结构与算法之美》12——二分查找

二分查找是一种非常简单易懂的快速查找算法，生活中随处可见，比如数字炸弹游戏。

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。

惊人的查找速度

二分查找是一种非常高效的查找算法，时间复杂度是O(logn)。

假设数据大小是n，每次查找后数据都会缩小为原来的一半，也就是除以2。最坏情况下，直到查找区间被缩小为空，才停止。

 

可以看出这是一个等比数列，其中n/2^k=1时，k就是总共缩小的次数，求得k=log2(n)，所以时间复杂度是O(logn)。

代码实现

非递归实现：

public int Find(int[] datas, int value)
{
    if (datas == null || datas.Length == 0) return -1;
 
    int start = 0, end = datas.Length - 1;
    int mid;
    while (start <= end)
    {
        mid = start + (end - start) / 2;
        if (value == datas[mid])
        {
            return mid;
        }
        else if (value < datas[mid])
        {
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }
 
    return -1;
}

递归实现：

递推公式：

if datas[mid] == value return mid;

if datas[mid] < value return fn(datas,value,mid+1,end)

if datas[mid] > value return fn(datas,value,start,mid-1)

终止条件：

start>end

public int FindByRecursion(int[] datas, int value)
{
    return FindInternallyByRecursion(datas, value, 0, datas.Length - 1);
}
 
private int FindInternallyByRecursion(int[] datas, int value, int start, int end)
{
    if (datas == null || datas.Length == 0) return -1;
 
    if (start > end) return -1;
 
    int mid = start + (end - start) / 2;
 
    if (value == datas[mid])
    {
        return mid;
    }
    else if (value < datas[mid])
    {
        end = mid - 1;
        return FindInternallyByRecursion(datas, value, start, end);
    }
    else
    {
        start = mid + 1;
        return FindInternallyByRecursion(datas, value, start, end);
    }
}

二分查找容易出错的地方

1. 循环退出条件

注意是low<=high，而不是low<high。

2. mid的取值

mid=(low+high)/2有可能溢出，改进方法是mid=low+(high-low)/2，进一步改为mid=low+((high-low)>>1)。

3. low和high的更新

low=mid+1, high=mid-1。注意这里的+1和-1，写成low=mid或者high=mid，就可能会发生死循环。

二分查找应用场景的局限性

1. 二分查找依赖的是顺序表结构，简单点说就是数组。

2. 二分查找针对的是有序数组。

3. 数据量太小不适合二分查找。

4. 数据量太大也不适合二分查找。

二分查找的变体

二分查找虽然原理极其简单，但是想写出没有Bug的二分查找并不容易。

下面介绍四种常见的二分查找变形问题：

变体一：查找第一个值等于给定值的元素

/**
         * 查找第一个值等于给定值的元素
         */
public int FindFirst(int[] datas, int value)
{
    if (datas == null || datas.Length == 0) return -1;
 
    int start = 0, end = datas.Length - 1;
    int mid;
    while (start <= end)
    {
        mid = start + (end - start) / 2;
 
        if (value < datas[mid])
        {
            end = mid - 1;
        }
        else if (value > datas[mid])
        {
            start = mid + 1;
        }
        else
        {
            if ((mid == 0) || (datas[mid - 1] != value)) return mid;
            else end = mid - 1;
        }
    }
 
    return -1;
}

变体二：查找最后一个值等于给定值的元素

/**
         * 查找最后一个值等于给定值的元素
         */
public int FindLast(int[] datas, int value)
{
    if (datas == null || datas.Length == 0) return -1;
 
    int start = 0, end = datas.Length - 1, n = datas.Length;
    int mid;
    while (start <= end)
    {
        mid = start + (end - start) / 2;
 
        if (value < datas[mid])
        {
            end = mid - 1;
        }
        else if (value > datas[mid])
        {
            start = mid + 1;
        }
        else
        {
            if ((mid == n - 1) || (datas[mid + 1] > value)) return mid;
            else start = mid + 1;
        }
    }
 
    return -1;
}

变体三：查找第一个大于等于给定值的元素

/**
         * 查找第一个值大于等于（不小于）给定值的元素
         */
public int FindFirstNotLessThan(int[] datas, int value)
{
    if (datas == null || datas.Length == 0) return -1;
 
    int start = 0, end = datas.Length - 1;
    int mid;
    while (start <= end)
    {
        mid = start + (end - start) / 2;
 
        if (value <= datas[mid])
        {
            if ((mid == 0) || (datas[mid - 1] < value)) return mid;
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }
 
    return -1;
}

变体四：查找最后一个小于等于给定值的元素

/**
         * 查找最后一个值大于等于（不小于）给定值的元素
         */
public int FindLastNotMoreThan(int[] datas, int value)
{
    if (datas == null || datas.Length == 0) return -1;
 
    int start = 0, end = datas.Length - 1, n = datas.Length;
    int mid;
    while (start <= end)
    {
        mid = start + (end - start) / 2;
 
        if (value < datas[mid])
        {
            end = mid - 1;
        }
        else
        {
            if ((mid == n - 1) || (datas[mid + 1] > value)) return mid;
            start = mid + 1;
        }
    }
 
    return -1;
}