字符串二分：最长重复子数组

此类题目考察"左边界"与"右边界"二分的精确实现。

在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）

public int[] searchRange(int[] nums, int target) {
    return new int[]{leftBound(nums, target), rightBound(nums, target)};
}

// 查找第一个 == target 的位置
private int leftBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    // lo 是第一个 >= target 的位置
    if (lo >= nums.length || nums[lo] != target) return -1;
    return lo;
}

// 查找最后一个 == target 的位置
private int rightBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    // lo - 1 是最后一个 <= target 的位置
    if (lo == 0 || nums[lo - 1] != target) return -1;
    return lo - 1;
}

寻找峰值（LeetCode 162）

峰值 = 比两侧都大的元素（边界视为 -∞）。

关键：中间元素与右边比较，选择往上坡走。

public int findPeakElement(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[mid + 1]) hi = mid;  // 右侧下坡，峰值在左
        else lo = mid + 1;                         // 右侧上坡，峰值在右
    }
    return lo;
}

搜索插入位置（LeetCode 35）

返回 target 应该插入的位置（即第一个 >= target 的位置）。

public int searchInsert(int[] nums, int target) {
    int lo = 0, hi = nums.length;  // 注意 hi = length，非 length-1
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

计数并找目标（多个相关题）

利用左右边界之差快速统计某值的出现次数：

int count = rightBound(nums, target) - leftBound(nums, target) + 1;
// 如果 leftBound 返回 -1，则 count = 0

总结