简介

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

顾名思义，二分查找就是从中间开始查找，如果中间的值比目标值大，则结果要么在左边，要么不存在，反之则结果要么在右边，要么不存在，以此类推进行下一步查找……

二分查找的运行时间为对数时间：
$$
O(log_2n)
$$
假设从 [0,99] 中查找目标位置最多只需要查找 7 次（2^6 < 100 < 2^7）

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class BinarySearch {

    /**
     * 重载二分查找
     *
     * @param arr    需要查找的目标数组
     * @param target 需要查找的值
     * @return 返回查找的值在数组中的索引，如果不存在，则返回0
     */
    public int binarySearch(int[] arr, int target) {
        return binarySearch(arr, 0, arr.length - 1, target);
    }

    /**
     * 二分查找
     *
     * @param arr   需要查找的数组
     * @param left  查找的左端点
     * @param right 查找的右端点
     * @param value 需要查找的值
     * @return 返回查找的值在数组中的索引，如果不存在，则返回0
     */
    public int binarySearch(int[] arr, int left, int right, int value) {
        if (arr[0] > value || arr[arr.length - 1] < value || right - left < 0) {
            return -1;
        }
        int mid = (left + right) / 2;

        if (arr[mid] == value) {
            return mid;
        } else if (arr[mid] > value) {
            return binarySearch(arr, left, mid - 1, value);
        } else {
            return binarySearch(arr, mid + 1, right, value);
        }
    }
}

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class BinarySearch2 {

    /**
     * 二分查找
     *
     * @param arr    需要查找的数组
     * @param target 需要查找的值
     * @return 返回查找的值在数组中的索引，如果不存在，则返回0
     */
    public int binarySearch(int[] arr, int target) {

        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;         //找到直接返回
            } else if (arr[mid] > target) {
                right = mid - 1;    //还要继续从左边查找
            } else {
                left = mid + 1;     //还要继续从右边查找
            }
        }
        //未找到结果，返回-1
        return -1;
    }
}

mid 的计算：

  • mid = (left + right) / 2
  • mid = left + (right - left) / 2

l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。