什么是二分查找？

二分查找（Binary Search）是一种在 有序数组 中查找某一特定元素的搜索算法。其工作原理是：

1. 从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束。
2. 如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样从中间元素开始比较。
3. 如果在某一步骤数组为空，则代表找不到。
4. 重复以上过程，直到找到目标值或者确定目标值不存在于数组中。

这种搜索算法每一次比较都使搜索范围缩小一半，因此其时间复杂度为 O(log n)。

不同实现版本的分析

以下是您提供的几种 Java 二分查找实现的详细分析：

核心变量:

• a: 输入的有序数组。
• target: 要查找的目标值。
• i: 搜索区间的左边界（起始索引）。
• j: 搜索区间的右边界（结束索引）。
• m: 搜索区间的中间索引。
• candidate: 用于记录潜在匹配目标值的索引（主要用于查找边界元素）。

注意: >>> 1 是无符号右移一位，等价于 / 2，但可以避免整数溢出问题 (i + j) 可能超过 Integer.MAX_VALUE。

1. binarySearch (基础版本 - while (i <= j))

public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length - 1; // [i, j]
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {       // 目标在左侧
            j = m - 1;             // 新区间 [i, m-1]
        } else if (a[m] < target) { // 目标在右侧
            i = m + 1;             // 新区间 [m+1, j]
        } else {                   // 找到了
            return m;
        }
    }
    return -1; // 未找到
}

• 区间定义: 闭区间 [i, j]。
• 循环条件: i <= j，表示当 i == j 时，区间 [i, i] 仍然有效，包含一个元素，需要检查。
• 边界更新:
  • target < a[m]: 目标在左侧，m 以及 m 右边的元素肯定不是，所以 j 变为 m - 1。
  • a[m] < target: 目标在右侧，m 以及 m 左边的元素肯定不是，所以 i 变为 m + 1。
  • a[m] == target: 直接返回 m。
• 未找到: 当循环结束时（i > j），表示区间为空，目标不存在，返回 -1。

示例: a = [2, 5, 7, 8, 11, 12], target = 13

示例: a = [2, 5, 7, 8, 11, 12], target = 8

2. binarySearch (变种 - while (i < j))

public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length; // [i, j)
    while (i < j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {        // 目标在左侧
            j = m;                  // 新区间 [i, m)
        } else if (a[m] < target) { // 目标在右侧
            i = m + 1;              // 新区间 [m+1, j)
        } else {                    // 找到了
            return m;
        }
    }
    return -1; // 未找到 (循环结束时 i == j)
}

• 区间定义: 左闭右开区间 [i, j)。j 初始化为 a.length，表示不包含索引 j。
• 循环条件: i < j，表示当 i == j 时，区间 [i, i) 为空，循环结束。
• 边界更新:
  • target < a[m]: 目标在左侧（可能等于 a[m] 左边的元素），m 可能是目标，但 m 右边的肯定不是。新区间是 [i, m)，所以 j = m。
  • a[m] < target: 目标在右侧，m 以及 m 左边的元素肯定不是，所以 i 变为 m + 1。新区间 [m+1, j)。
  • a[m] == target: 直接返回 m。
• 未找到: 当循环结束时（i == j），表示区间 [i, i) 为空，目标不存在，返回 -1。

示例: a = [2, 5, 7, 8, 11, 12], target = 13

示例: a = [2, 5, 7, 8, 11, 12], target = 8

3. binarySearchBalance (平衡变种 - while (1 < j - i))

public static int binarySearchBalance(int[] a, int target) {
    int i = 0, j = a.length; // (i, j) - 搜索范围在开区间? 实际更像是 [i, j)
    while (1 < j - i) {      // 循环直到区间大小 <= 1
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m;           // 新区间 [i, m)
        } else {
            i = m;           // 新区间 [m, j)
        }
    }
    // 循环结束时 j - i <= 1，区间为 [i, i+1) 或 [i, i)
    // 此时 potential target 在索引 i
    return (i < a.length && a[i] == target) ? i : -1;
}

• 区间定义: 看起来是左闭右开 [i, j)。j 初始化为 a.length。
• 循环条件: 1 < j - i，意味着循环在区间大小 (j - i) 大于 1 时继续。当 j - i <= 1 (即区间大小为 0 或 1) 时退出。
• 边界更新:
  • target < a[m]: 目标在 m 左侧，更新右边界 j = m。
  • target >= a[m]: 目标在 m 或 m 右侧，更新左边界 i = m。注意这里包含了等于的情况。
• 后处理: 循环结束后，区间大小为 0 或 1。如果目标存在，它必然在索引 i 处（因为 else 分支将 i 更新为 m）。需要检查 a[i] 是否确实等于 target。同时要检查 i 是否越界（例如在空数组或查找比所有元素都小的目标时）。
• 未找到: 如果最后 a[i] != target 或 i 越界，返回 -1。

示例: a = [2, 5, 7, 8, 11, 12], target = 13

示例: a = [2, 5, 7, 8, 11, 12], target = 8

4. binarySearchLeftmost1 (查找最左目标 - candidate 记录)

public static int binarySearchLeftmost1(int[] a, int target) {
    int i = 0, j = a.length - 1; // [i, j]
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;          // [i, m-1]
        } else if (a[m] < target) {
            i = m + 1;          // [m+1, j]
        } else {                // a[m] == target
            candidate = m;      // 记录候选位置
            j = m - 1;          // 继续向左查找看是否有更左的 [i, m-1]
        }
    }
    return candidate;
}

• 目标: 找到数组中等于 target 的最左边的元素的索引。如果不存在，返回 -1。
• 区间定义: 闭区间 [i, j]。
• 核心逻辑: 使用 candidate 变量记录最后一次找到 target 的位置。当 a[m] == target 时，不立即返回，而是记录下 m 作为潜在的最左索引，然后继续在左半部分 [i, m-1] 搜索，看是否存在更靠左的 target。
• 边界更新:
  • 当 a[m] == target 时，将 candidate 更新为 m，并将 j 更新为 m - 1，试图在左侧找到更小的索引。
• 未找到: 如果从未找到 target，candidate 保持初始值 -1。

示例: a = [1, 2, 3, 3, 3, 4, 5], target = 3

5. binarySearchRightmost1 (查找最右目标 - candidate 记录)

public static int binarySearchRightmost1(int[] a, int target) {
    int i = 0, j = a.length - 1; // [i, j]
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;          // [i, m-1]
        } else if (a[m] < target) {
            i = m + 1;          // [m+1, j]
        } else {                // a[m] == target
            candidate = m;      // 记录候选位置
            i = m + 1;          // 继续向右查找看是否有更右的 [m+1, j]
        }
    }
    return candidate;
}

• 目标: 找到数组中等于 target 的最右边的元素的索引。如果不存在，返回 -1。
• 区间定义: 闭区间 [i, j]。
• 核心逻辑: 与 Leftmost1 类似，使用 candidate 记录。当 a[m] == target 时，记录下 m，然后继续在右半部分 [m+1, j] 搜索，看是否存在更靠右的 target。
• 边界更新:
  • 当 a[m] == target 时，将 candidate 更新为 m，并将 i 更新为 m + 1，试图在右侧找到更大的索引。
• 未找到: 如果从未找到 target，candidate 保持初始值 -1。

示例: a = [1, 2, 3, 3, 3, 4, 5], target = 3

6. binarySearchRightmost (查找最右目标的变种 - 返回 i-1)

public static int binarySearchRightmost(int[] a, int target) {
    int i = 0, j = a.length - 1; // [i, j]
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;          // [i, m-1]
        } else {                // target >= a[m]
            i = m + 1;          // [m+1, j]
        }
    }
    // 循环结束时, i 是第一个 > target 的元素的索引 (或 a.length)
    // 因此 i-1 是最后一个 <= target 的元素的索引
    // 如果 a[i-1] == target, 则 i-1 就是最右侧的 target
    // 需要检查 i-1 是否有效且 a[i-1] == target (虽然代码没显式检查，但这是其含义)
    return i - 1;
}

• 目标: 找到小于或等于 target 的最右元素的索引。如果该元素恰好等于 target，则它就是最右边的 target。
• 区间定义: 闭区间 [i, j]。
• 核心逻辑: 这个版本的关键在于 else 分支的处理：当 target >= a[m] 时，将 i 更新为 m + 1。这意味着我们总是在寻找第一个大于 target 的元素的位置。
• 循环结束: 当循环结束时 (i > j)，i 指向的是第一个大于 target 的元素的位置（或者是 a.length 如果 target 比所有元素都大或相等）。因此，i-1 就是最后一个小于或等于 target 的元素的位置。
• 返回值: 返回 i - 1。
  • 如果数组中存在 target，并且 a[i-1] == target，那么 i-1 就是最右边的 target 的索引。
  • 如果 target 比所有元素都小，i 最终为 0，返回 -1。
  • 如果 target 比所有元素都大，i 最终为 a.length，返回 a.length - 1（数组最后一个元素的索引）。
  • 如果 target 介于数组元素之间但不存在，i-1 指向小于 target 的最大元素的索引。
• 注意: 这个实现直接返回 i-1，它不保证返回的索引处的元素一定等于 target。它返回的是 小于或等于 target 的最右元素的索引。如果要确保找到的是 target，调用者需要额外检查 a[i-1] == target 并处理 i=0 (即 i-1 = -1) 的情况。

示例: a = [1, 2, 3, 3, 3, 4, 5], target = 3

示例: a = [1, 2, 4, 5], target = 3

7. binarySearchLeftmost (查找最左目标的变种 - 返回 i)

public static int binarySearchLeftmost(int[] a, int target) {
    int i = 0, j = a.length - 1; // [i, j]
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target <= a[m]) {    // target <= a[m]
            j = m - 1;          // [i, m-1]
        } else {                // target > a[m]
            i = m + 1;          // [m+1, j]
        }
    }
    // 循环结束时, i 是第一个 >= target 的元素的索引 (或 a.length)
    // 如果 a[i] == target, 则 i 就是最左侧的 target
    // 需要检查 i 是否越界且 a[i] == target (虽然代码没显式检查，但这是其含义)
    return i;
}

• 目标: 找到大于或等于 target 的最左元素的索引。如果该元素恰好等于 target，则它就是最左边的 target。
• 区间定义: 闭区间 [i, j]。
• 核心逻辑: 这个版本的关键在于 if 分支的处理：当 target <= a[m] 时，将 j 更新为 m - 1。这意味着我们总是在寻找第一个大于等于 target 的元素的位置。
• 循环结束: 当循环结束时 (i > j)，j 指向的是最后一个小于 target 的元素的位置（或者是 -1 如果 target 比所有元素都小或相等）。i 指向的是第一个大于或等于 target 的元素的位置（或者是 a.length 如果 target 比所有元素都大）。
• 返回值: 返回 i。
  • 如果数组中存在 target，并且 a[i] == target，那么 i 就是最左边的 target 的索引。
  • 如果 target 比所有元素都小，i 最终为 0，返回 0。
  • 如果 target 比所有元素都大，i 最终为 a.length，返回 a.length。
  • 如果 target 介于数组元素之间但不存在，i 指向第一个大于 target 的元素的索引。
• 注意: 这个实现直接返回 i，它不保证返回的索引处的元素一定等于 target。它返回的是 大于或等于 target 的最左元素的索引。如果要确保找到的是 target，调用者需要额外检查 i 是否在数组界限内 (i < a.length) 并且 a[i] == target。

示例: a = [1, 2, 3, 3, 3, 4, 5], target = 3

示例: a = [1, 2, 4, 5], target = 3

边界问题说明

二分查找的边界问题主要体现在：

1. 区间定义:
   • [i, j] (闭区间): 循环条件通常是 i <= j。当 i == j 时，区间还有一个元素，需要检查。更新时，如果不匹配 m，则新区间排除 m（j = m - 1 或 i = m + 1）。
   • [i, j) (左闭右开): 循环条件通常是 i < j。当 i == j 时，区间为空，循环结束。j 初始化为 a.length。更新时，如果 target < a[m]，则 m 可能是目标，新右边界为 m (j = m)；如果 target > a[m]，则 m 不可能是目标，新左边界为 m + 1 (i = m + 1)。
2. 循环条件:
   • i <= j: 允许 i 和 j 相等，处理单元素区间。
   • i < j: 当 i 和 j 相等时退出，适用于 [i, j) 区间。
   • 1 < j - i: 退出时区间大小为 0 或 1，需要后处理。
3. 中间值计算: m = (i + j) >>> 1 是防止 i + j 溢出的标准做法。如果写成 m = i + (j - i) / 2 也可以。
4. 目标未找到:
   • 返回 -1: 明确表示未找到。适用于基础查找和使用 candidate 的版本。
   • 返回 i 或 i-1: 这些版本返回的是一个边界索引（第一个 >= target 的或最后一个 <= target 的），即使 target 不存在，也会返回一个有意义的索引（表示插入点或邻近值）。调用者需要根据 i 的值和 a[i] 或 a[i-1] 的值来判断 target 是否真的存在。
5. 数组为空: 需要在函数入口处处理，否则 a.length - 1 会出错 (对于 j = a.length - 1 的初始化)。j = a.length 的初始化方式对空数组更健壮。
6. 查找边界 (Leftmost/Rightmost):
   • candidate 方法: 逻辑相对清晰，找到一个匹配项后，记录下来并继续向一个方向搜索。
   • 返回 i / i-1 方法: 代码更简洁，但需要理解循环不变式以及 i 在循环结束时的确切含义。需要调用者进行后处理（检查索引有效性及值是否匹配）。

各自的优劣情况

总结:

• 对于基础查找（判断是否存在），binarySearch (i <= j) 或 binarySearch (i < j) 都可以，前者可能更符合初学者的直觉。
• 对于查找最左/最右边界，使用 candidate 的 Leftmost1/Rightmost1 方法逻辑最清晰明确，不易出错。
• Leftmost (返回 i) 和 Rightmost (返回 i-1) 的变种更简洁，性能可能微乎其微地好一点（少了变量赋值），但需要调用者更深入地理解其返回值含义并进行必要的后处理检查，它们分别对应于查找 第一个大于等于 target 的位置和 最后一个小于等于 target 的位置，常用于实现类似 C++ STL 中的 lower_bound 和 upper_bound（或其变种）的功能。
• binarySearchBalance 相对不常用，其优势不明显。

选择哪种实现取决于具体需求（是精确查找、找边界还是找插入点）以及个人或团队的编码风格偏好。对于需要精确找到最左/最右 target 并处理不存在情况的场景，candidate 方法通常是更安全、更易读的选择。