10.3 二分搜尋邊界¶

10.3.1 查詢左邊界¶

Question

給定一個長度為 \(n\) 的有序陣列 nums ，其中可能包含重複元素。請返回陣列中最左一個元素 target 的索引。若陣列中不包含該元素，則返回 \(-1\) 。

回憶二分搜尋插入點的方法，搜尋完成後 \(i\) 指向最左一個 target ，因此查詢插入點本質上是在查詢最左一個 target 的索引。

考慮透過查詢插入點的函式實現查詢左邊界。請注意，陣列中可能不包含 target ，這種情況可能導致以下兩種結果。

插入點的索引 \(i\) 越界。
元素 nums[i] 與 target 不相等。

當遇到以上兩種情況時，直接返回 \(-1\) 即可。程式碼如下所示：

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

binary_search_edge.py

def binary_search_left_edge(nums: list[int], target: int) -> int:
    """二分搜尋最左一個 target"""
    # 等價於查詢 target 的插入點
    i = binary_search_insertion(nums, target)
    # 未找到 target ，返回 -1
    if i == len(nums) or nums[i] != target:
        return -1
    # 找到 target ，返回索引 i
    return i

binary_search_edge.cpp

/* 二分搜尋最左一個 target */
int binarySearchLeftEdge(vector<int> &nums, int target) {
    // 等價於查詢 target 的插入點
    int i = binarySearchInsertion(nums, target);
    // 未找到 target ，返回 -1
    if (i == nums.size() || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

binary_search_edge.java

/* 二分搜尋最左一個 target */
int binarySearchLeftEdge(int[] nums, int target) {
    // 等價於查詢 target 的插入點
    int i = binary_search_insertion.binarySearchInsertion(nums, target);
    // 未找到 target ，返回 -1
    if (i == nums.length || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

binary_search_edge.cs

/* 二分搜尋最左一個 target */
int BinarySearchLeftEdge(int[] nums, int target) {
    // 等價於查詢 target 的插入點
    int i = binary_search_insertion.BinarySearchInsertion(nums, target);
    // 未找到 target ，返回 -1
    if (i == nums.Length || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

binary_search_edge.go

/* 二分搜尋最左一個 target */
func binarySearchLeftEdge(nums []int, target int) int {
    // 等價於查詢 target 的插入點
    i := binarySearchInsertion(nums, target)
    // 未找到 target ，返回 -1
    if i == len(nums) || nums[i] != target {
        return -1
    }
    // 找到 target ，返回索引 i
    return i
}

binary_search_edge.swift

/* 二分搜尋最左一個 target */
func binarySearchLeftEdge(nums: [Int], target: Int) -> Int {
    // 等價於查詢 target 的插入點
    let i = binarySearchInsertion(nums: nums, target: target)
    // 未找到 target ，返回 -1
    if i == nums.endIndex || nums[i] != target {
        return -1
    }
    // 找到 target ，返回索引 i
    return i
}

binary_search_edge.js

/* 二分搜尋最左一個 target */
function binarySearchLeftEdge(nums, target) {
    // 等價於查詢 target 的插入點
    const i = binarySearchInsertion(nums, target);
    // 未找到 target ，返回 -1
    if (i === nums.length || nums[i] !== target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

binary_search_edge.ts

/* 二分搜尋最左一個 target */
function binarySearchLeftEdge(nums: Array<number>, target: number): number {
    // 等價於查詢 target 的插入點
    const i = binarySearchInsertion(nums, target);
    // 未找到 target ，返回 -1
    if (i === nums.length || nums[i] !== target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

binary_search_edge.dart

/* 二分搜尋最左一個 target */
int binarySearchLeftEdge(List<int> nums, int target) {
  // 等價於查詢 target 的插入點
  int i = binarySearchInsertion(nums, target);
  // 未找到 target ，返回 -1
  if (i == nums.length || nums[i] != target) {
    return -1;
  }
  // 找到 target ，返回索引 i
  return i;
}

binary_search_edge.rs

/* 二分搜尋最左一個 target */
fn binary_search_left_edge(nums: &[i32], target: i32) -> i32 {
    // 等價於查詢 target 的插入點
    let i = binary_search_insertion(nums, target);
    // 未找到 target ，返回 -1
    if i == nums.len() as i32 || nums[i as usize] != target {
        return -1;
    }
    // 找到 target ，返回索引 i
    i
}

binary_search_edge.c

/* 二分搜尋最左一個 target */
int binarySearchLeftEdge(int *nums, int numSize, int target) {
    // 等價於查詢 target 的插入點
    int i = binarySearchInsertion(nums, numSize, target);
    // 未找到 target ，返回 -1
    if (i == numSize || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

binary_search_edge.kt

/* 二分搜尋最左一個 target */
fun binarySearchLeftEdge(nums: IntArray, target: Int): Int {
    // 等價於查詢 target 的插入點
    val i = binarySearchInsertion(nums, target)
    // 未找到 target ，返回 -1
    if (i == nums.size || nums[i] != target) {
        return -1
    }
    // 找到 target ，返回索引 i
    return i
}

binary_search_edge.rb

### 二分搜尋最左一個 target ###
def binary_search_left_edge(nums, target)
  # 等價於查詢 target 的插入點
  i = binary_search_insertion(nums, target)

  # 未找到 target ，返回 -1
  return -1 if i == nums.length || nums[i] != target

  i # 找到 target ，返回索引 i
end

binary_search_edge.zig

[class]{}-[func]{binarySearchLeftEdge}

視覺化執行

全螢幕觀看 >

10.3.2 查詢右邊界¶

那麼如何查詢最右一個 target 呢？最直接的方式是修改程式碼，替換在 nums[m] == target 情況下的指標收縮操作。程式碼在此省略，有興趣的讀者可以自行實現。

下面我們介紹兩種更加取巧的方法。

1. 複用查詢左邊界¶

實際上，我們可以利用查詢最左元素的函式來查詢最右元素，具體方法為：將查詢最右一個 target 轉化為查詢最左一個 target + 1。

如圖 10-7 所示，查詢完成後，指標 \(i\) 指向最左一個 target + 1（如果存在），而 \(j\) 指向最右一個 target ，因此返回 \(j\) 即可。

圖 10-7 將查詢右邊界轉化為查詢左邊界

請注意，返回的插入點是 \(i\) ，因此需要將其減 \(1\) ，從而獲得 \(j\) ：