二分搜索算法變體：查找區間邊界的 Java 實現與複雜度分析

問題描述

給定已排序數組 a[0:n-1]，實現二分搜索：若目標值 x 存在，返回其位置作為 i 和 j；若不存在，返回 i 為小於 x 的最大元素位置，j 為大於 x 的最小元素位置。

算法邏輯

遞歸二分搜索，維護區間 [i, j]：

• 若 i > j：未找到，answer[0]=j（最後一個 < x），answer[1]=i（第一個 > x）
• 若 x == arr[mid]：找到，i=j=mid
• 若 x < arr[mid]：遞歸左半部 [i, mid-1]
• 若 x > arr[mid]：遞歸右半部 [mid+1, j]

Java 完整實現

import java.util.Arrays;
import java.util.Scanner;

public class BinarySearchBounds {
    static int target;

    // 遞歸查找，answer[0]=i, answer[1]=j
    static void search(int left, int right, int[] arr, int[] answer) {
        if (left > right) { // 未找到
            answer[0] = right;  // 最大的 < x
            answer[1] = left;   // 最小的 > x
            return;
        }
        int mid = left + (right - left) / 2;
        if (target == arr[mid]) {
            Arrays.fill(answer, mid);
        } else if (target < arr[mid]) {
            search(left, mid - 1, arr, answer);
        } else {
            search(mid + 1, right, arr, answer);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) arr[i] = scanner.nextInt();
            target = scanner.nextInt();
            int[] answer = new int[2];
            search(0, n - 1, arr, answer);
            System.out.println(answer[0] + " " + answer[1]);
        }
        scanner.close();
    }
}

複雜度分析

• 時間複雜度：O(log n)。每次遞歸區間減半，遞歸深度 ≤ log₂n。
• 空間複雜度：O(log n)。遞歸調用棧深度。可改寫為迭代版本優化至 O(1)。

關鍵細節

1. 中間點計算：用 left + (right-left)/2 避免溢出
2. 邊界條件：left > right 時 right 指向最後一個 < x，left 指向第一個 > x，符合插入位置語義
3. 數組有序性：前提是嚴格遞增，若有重複元素需明確定義「最大/最小位置」

迭代版優化（O(1) 空間）

static void searchIterative(int[] arr, int[] ans) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (target == arr[mid]) { ans[0] = ans[1] = mid; return; }
        else if (target < arr[mid]) r = mid - 1;
        else l = mid + 1;
    }
    ans[0] = r; ans[1] = l; // 退出時 l = r+1，r 為最後 < x，l 為第一 > x
}

應用場景

此變體常用於：區間查詢前驅/後繼、離散化坐標壓縮、動態維護有序集合的 lower_bound/upper_bound 邏輯。