二分查找一个数首次与最后出现的位置

[题目描述]

查找顺序数组中某个数首次或最后一次出现的位置。

首次出现：

public class BinarySearch {
    public static int left(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else hi = mid;
        }
        if (a[hi] == key) //或 lo
            return hi;
        return -1;
    }

    public static void main(String[] args) {

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1. hi = mid找到下标时不返回，存入 hi， 逐步收缩右边界，找不到时则按照传统二分计算。

2. 循环结束条件。

   退出前一步可能 mid = lo 或mid = (hi - lo) / 2 。

   mid = (hi - lo) / 2 时：

   • 如果 a[mid] = key，hi = mid，也就是下一种情况（mid = lo ）。
   • 如果 a[mid] < key，lo = hi，退出循环。
     
     

   mid = lo 时：

   • 如果 a[mid] = key，hi = mid = lo，退出循环。
   • 如果 a[mid] < key，lo = hi，退出循环。
   
   综上，退出循环时总有 `lo = hi`，所以，循环结束条件如果设置成 <= 将会无限循环。

3. 循环退出时还未判断 hi 处的值，所以 if (a[hi] == key)用来判断上面循环未判断的 hi 处的值是否等于 key。因为 lo = hi 所以此处也可换为 if (a[lo] == key)。

最后一次出现：

	public static int right(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2 + 1;
            if (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else lo = mid;
        }
        if (a[lo] == key) //或 hi
            return lo;
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

利用对称性（便于理解），类比上面的算法，很容易想到将else hi = mid;换成else lo = mid;，将下标存入 lo，收缩左边界。

但此时有一点不对称，就是计算 mid 时是取整计算，去掉小数点后的数，如果要对称的话就要在原始 mid 的基础上加 1。即 int mid = lo + (hi - lo) / 2 + 1;