二分查找法

算法思想

有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。

一个情景：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

参考：https://baijiahao.baidu.com/s?id=1669750553177807262&wfr=spider&for=pc

使用条件

1. 有序
2. 顺序存储

优缺点

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

使用条件：查找序列是顺序结构，有序。

复杂度

时间复杂度：O(logn)

空间复杂度：O(1) (递归为O(log))

Java实现

迭代实现

/**
 * 二分查找法 循环实现
 *
 * @param arr 待查找数组
 * @param num 待查询数
 * @return num在arr的索引位置，不存在返回-1
 */
public int binarySearchByLoop(int[] arr, int num) {
    int start = 0, end = arr.length - 1;
    //临界值快速判断（num小于数组左边或者大于右边，必定找不到——二分查找前提，数组有序）
    if (arr[start] > num || arr[end] < num) {
        return - 1;
    }
    while (start <= end) {
        //防止出现越界
        int mid = start + (end - start) / 2;
        if (num == arr[mid]) {
            return mid;
        } else if (num < arr[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return - 1;
}

递归实现

/**
 * 二分查找法 循环实现
 *
 * @param arr   待查找数组
 * @param num   待查询数
 * @param start 起始位置
 * @param end   结束位置
 * @return num在arr的索引位置，不存在返回-1
 */
public int binarySearchByRecursion(int[] arr, int num, int start, int end) {
    //临界值快速判断（num小于数组左边或者大于右边，必定找不到——二分查找前提，数组有序）   start > end 为递归终止条件
    if (arr[start] > num || arr[end] < num || start > end) {
        return - 1;
    }
    int mid = start + (end - start) / 2;
    if (num == arr[mid]) {
        return mid;
    } else if (num < arr[mid]) {
        return binarySearchByRecursion(arr, num, start, mid - 1);
    } else {
        return binarySearchByRecursion(arr, num, mid + 1, end);
    }
}