二分查找算法

一个游戏：

讲二分查找算法之前，先讲个猜数字游戏的规则：从1-100中猜测一个预先设置的数字，猜测者每次猜测一个数字，设定数字的人会告知比猜测的数字大或者小或者猜对了。

### ·简单算法：

我们可以每次从1开始猜测，第二次猜2，依次增加，如果数字设置的小还好，如果设置较大，那么猜测的次数将大大增加，我们称这种算法为简单算法。

·二分查找算法（又叫折半算法）：

正确的做法是从50开始猜，如果大了，我们第二次开始猜25，如果小了，我们就猜75，以此类推，这样1-100中的数字，我们一定能在7次猜对对方给出的数字，这就是二分查找算法的思路。

二分查找算法图示：

二分算法次数：

样本放大，如果是从1-1亿中猜数字，那么简单猜测的步数就是1亿次，而二分查找算法的步数是27次，算法的威力就提现出来了。二分查找算法的步数的计算公式是log₂n（n是数字范围）

~算法的代码实现（Java版）：

1、循环实现二分查找算法

/**
 * 循环实现二分查找算法
 * @param list：需要查找的有序数组
 * @param result：查找的目标值
 * @return
 */
public static int binarySearch(int[] list, int result){
    int low = 0;
    int high = list.length - 1;
    if (result < list[0] || result > list[high]){
        return -1;
    }

    while (low <= high){
        int mid = (low + high) / 2;
        int guess = list[mid];
        if (guess == result){
            return mid;
        }
        if (guess > result){
            high = mid - 1;
        }else {
            low = mid + 1;
        }
    }
    return -1;
}

2、递归实现二分查找算法 2、递归实现二分查找算法

/**
 * 递归实现二分查找算法
 * @param list：需要查找的有序数组
 * @param result：查找的目标值
 * @param low：有序数组的最小值
 * @param high：有序数组的最大值
 * @return
 */
public static int recursionBinarySearch(int[] list, int result, int low, int high){
    if (result < list[0] || result > list[high]){
        return -1;
    }

    int mid = (low + high) / 2;
    if (list[mid] > result){
        return  recursionBinarySearch(list, result, low, mid - 1);
    }else if (list[mid] < result){
        return recursionBinarySearch(list, result, mid + 1, high);
    }else {
        return mid;
    }
}

二分查找算法的时间复杂度：二分查找算法的时间复杂度：

推导方法：从上图来分析，假设查找的次数为K

第1次查找剩余元素为：N/2^1(K=1)
第2次查找剩余元素为：N/2^2(K=2)
……
第N次查找剩余元素为：N/2^K
从上面的推导可以得出N/2^K >= 1(也就是一定会有一个元素)，大O标识的最糟糕的时间复杂度，那么，按最坏的结果计算，查到最后一个元素才找到最后的数字，也就是N/2^K = 1，从而可以推导出N = 2^K，进而推导出：K = log₂N

所以二分查找算法的时间复杂度为：O（log₂n）

二分查找算法优点：

查找次数较少
查找速度快
平均性能好

二分查找算法缺点：

要求列表为有序列表
插入删除困难
不适用于经常变动的数据列表