什么是二分法查找

二分查找也称折半查找（BinarySearch），它是一种采用分治策略的算法，他将问题分解为规模更小的的子问题，分而治之，逐一解决。采用二分法查找的前提条件是：要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分法查找使用场景

二分法查找适用于数据量较大时，但是数据需要先排好顺序。对于我们很多人来说，还是用于面试……

二分法查找算法设计

设排序元素序列（升序）存储在 arrs 数组，begin、end 指定查找范围，keyword 是指定查找的值。

  1. 每次从子序列中间 mid 开始比较 mid = (begin + end) / 2，如果 keyword 与 arrs[mid] 元素相等，则查找成功；否则根据根据 keyword 大小缩小查找范围，若 keyword 较小，则继续在子序列前半段 begin ~ (mid - 1) 查找；反之在后半段 (mid - 1) ~ end查找。
  2. 重复 1，直到查找成功，当 begin、end 表示范围失效时，返回 -1 表示查找失败。

时间复杂度

最快：O(1)
最坏：O(logn)
平均时间复杂度：O(logn)

Java 实现

循环实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 二分查找
 * @param arr
 * @param value
 * @return -1 则查找失败
 */
public static int binarySearch(int[] arr, int value) {
    int begin = 0;
    int end = arr.length - 1;
    int mid;
    while (begin <= end) { // 边界有效
        mid = (begin + end) / 2; // 计算中界
        if (arr[mid] == value) { // 如果两个值相等
            return mid;
        } else if (value > arr[mid]) { // value 较小
            begin = mid + 1; //
        } else { // value 较大
            end = mid - 1;
        }
    }
    return -1;
}

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 递归实现二分法查找
 * @param arr   [排序完成的线性表]
 * @param value [查找的元素]
 * @param begin [从第几个元素开始]
 * @param end   [数组长度 - 1]
 * @return -1 则查找失败
 */
public static int binarySearch(int[] arr, int value, int begin, int end) {
    int mid = (begin + end) / 2;
    // 无效边界
    if (begin > end) {
        return -1;
    }
    if (arr[mid] == value) {
        return mid;
    } else if (value > arr[mid]) { // value 较小 
        begin = mid + 1;
    } else {
        end = mid - 1;
    }
    return binarySearch(arr, value, begin, end);
}