豁蒙楼

二分查找

发表于 分类于 Disqus：

链接

二分查找算法详解

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class binarysearch {
    public static void main(String[] args){
        int[] a = {1, 2, 2, 2, 3};
        System.out.println(right_bound(a, 2));
    }
    // 默认数组有序
    static int binarySearch(int[] arr, int target){
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right){
            int mid = (left + right) >> 1;
            if (target == arr[mid]){
                return mid;
            } else if (arr[mid] < target){
                left = mid + 1;
            } else if (arr[mid] > target){
                right = mid - 1; 
            }
        }
        return -1;
    }

    // 寻找左侧边界
    static int left_bound(int[] arr, int target){
        int n = arr.length;
        int left, right;
        left = 0;
        right = n;

        while(left < right){
            int mid = (left + right) >> 1;
            if (arr[mid] == target){
                right = mid;
            } else if (arr[mid] > target){
                right = mid;
            } else if (arr[mid] < target){
                left = mid + 1;
            }
        }
        if (left == arr.length) return -1;
        return (arr[left] == target) ? left : -1;
    }

    // 寻找右侧边界
    static int right_bound(int[]arr, int target){
        int n = arr.length;
        int left, right;
        left = 0;
        right = n;

        while(left < right){
            int mid = (left + right) >> 1;
            if (arr[mid] == target){
                left = mid + 1;
            } else if (arr[mid] > target){
                right = mid;
            } else if (arr[mid] < target){
                left = mid + 1;
            }
        }
        if (left == 0) return -1;
        return (arr[left - 1] == target) ? left - 1 : -1;
    }
}

注意点

  1. 确定左右边界时, 初始区间[0, arr.length)。
  2. 确定左边界时, 关键在于
1
2
3
if (arr[mid] == target){
    right = mid;
}

这是由于每次mid的判断将[Left, right) 分成两部分, 这样可以逐次剥除最右的等于target的元素

  1. 确定右边界时,
1
2
3
if (arr[mid] == target){
    left = mid + 1;
}

同样的，如果剥除最左的等于target的元素，由于区间左闭，需要去除mid。