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

时间复杂度是O(logn)

二分查找实现

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
public class BinarySearch {
    private int[] array;

    private BinarySearch(int[] array) {
        this.array = array;
    }

    private int binarySearch(int value) throws Exception {
        int lo = 0;
        int hi = array.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (array[mid] == value) {
                return mid;
            } else if (array[mid] > value) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) throws Exception {
        int[] array = { 1, 3, 6, 8, 9 };
        BinarySearch binarySearch = new BinarySearch(array);
        System.out.println(binarySearch.binarySearch(9));

    }
}

注意事项

循环退出条件是：start<=end，而不是start<end。

mid的取值可以优化，如使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因为如果start和end比较大的话，求和可能会发生int类型的值超出最大范围。

为了把性能优化到极致，可以将除以2转换成位运算，即start + ((end - start) >> 1)，相比除法运算来说，计算机处理位运算要快得多。

start和end的更新：start = mid - 1，end = mid + 1，若直接写成start = mid，end=mid，就可能会发生死循环。

使用条件

  • 二分查找依赖的是顺序表结构，即数组
  • 二分查找针对的是有序数据，因此只能用在插入、删除操作不频繁，一次排序多次查找的场景中
  • 数据量太小不适合二分查找，与直接遍历相比效率提升不明显。但有一个例外，就是数据之间的比较操作非常费时，比如数组中存储的都是长度超过300的字符串，那这是还是尽量减少比较操作使用二分查找吧
  • 数据量太大也不是适合用二分查找，因为数组需要连续的空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间

四种常见的二分查找变形问题

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * 查找第一个值等于给定值的元素
 */
public int binarySearch(int value){
    int lo = 0;
    int hi = array.length -1;
    while (lo <= hi){
        int mid = lo + (hi - lo)/2;
        if (array[mid] > value){
            hi = mid -1;
        }else if (array[mid]<value){
            lo = mid +1;
        }else {
            if (mid == 0 || array[mid -1]!= value){
                return mid;
            }else {
                hi = 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
/*
 * 查找最后一个值等于给定值的元素
 */
public int binarySearch3(int value) {
    int lo = 0;
    int hi = array.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (array[mid] > value) {
            hi = mid - 1;
        } else if (array[mid] < value) {
            lo = mid + 1;
        } else {
            if (mid == array.length - 1 || array[mid + 1] != value) {
                return mid;
            } else {
                lo = mid + 1;
            }
        }
    }
    return -1;
}

查找第一个大于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * 查找第一个大于等于给定值的元素
 */
public int binarySearch(int value) {
    int lo = 0;
    int hi = array.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (array[mid] >= value) {
            if (mid == 0 || array[mid - 1] < value) {
                return mid;
            } else {
                hi = mid - 1;
            }
        } else {
            lo = mid + 1;
        }
    }
    return -1;
}

查找最后一个小于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * 查找最后一个小于等于给定值的元素
 */

public int binarySearch5(int value) {
    int lo = 0;
    int hi = array.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (array[mid] <= value) {
            if (mid == (array.length - 1) || array[mid + 1] > value) {
                return mid;
            } else {
                lo = mid + 1;
            }
        } else {
            hi = mid - 1;
        }
    }

适用性分析

凡是能用二分查找解决的，绝大部分我们更倾向于用散列表或者二叉查找树，

即便二分查找在内存上更节省，但是毕竟内存如此紧缺的情况并不多。

求“值等于给定值”的二分查找确实不怎么用到，二分查找更适合用在”近似“查找问题上。比如上面讲几种变体。