C++二分查找邊界

查找左邊界

Question

給定一個長度為 n 的有序數(shù)組 nums ，數(shù)組可能包含重復(fù)元素。請返回數(shù)組中最左一個元素 target 的索引。若數(shù)組中不包含該元素，則返回 ?1 。

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

考慮通過查找插入點的函數(shù)實現(xiàn)查找左邊界。請注意，數(shù)組中可能不包含 target ，這種情況可能導(dǎo)致以下兩種結(jié)果。

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

當(dāng)遇到以上兩種情況時，直接返回 ?1 即可。

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;
}

查找右邊界

那么如何查找最右一個 target 呢？最直接的方式是修改代碼，替換在 nums[m] == target 情況下的指針收縮操作。代碼在此省略，有興趣的同學(xué)可以自行實現(xiàn)。

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

1.   復(fù)用查找左邊界

實際上，我們可以利用查找最左元素的函數(shù)來查找最右元素，具體方法為：將查找最右一個 target 轉(zhuǎn)化為查找最左一個 target + 1。

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

圖 10-7   將查找右邊界轉(zhuǎn)化為查找左邊界

binary_search_edge.cpp

/* 二分查找最右一個 target */
int binarySearchRightEdge(vector<int> &nums, int target) {
    // 轉(zhuǎn)化為查找最左一個 target + 1
    int i = binarySearchInsertion(nums, target + 1);
    // j 指向最右一個 target ，i 指向首個大于 target 的元素
    int j = i - 1;
    // 未找到 target ，返回 -1
    if (j == -1 || nums[j] != target) {
        return -1;
    }
    // 找到 target ，返回索引 j
    return j;
}

轉(zhuǎn)化為查找元素

我們知道，當(dāng)數(shù)組不包含 target 時，最終 i 和 j 會分別指向首個大于、小于 target 的元素。

因此，如圖 10-8 所示，我們可以構(gòu)造一個數(shù)組中不存在的元素，用于查找左右邊界。

• 查找最左一個 target ：可以轉(zhuǎn)化為查找 target - 0.5 ，并返回指針 i 。
• 查找最右一個 target ：可以轉(zhuǎn)化為查找 target + 0.5 ，并返回指針 j 。

圖 10-8   將查找邊界轉(zhuǎn)化為查找元素

代碼在此省略，值得注意以下兩點。

• 給定數(shù)組不包含小數(shù)，這意味著我們無須關(guān)心如何處理相等的情況。
• 因為該方法引入了小數(shù)，所以需要將函數(shù)中的變量 target 改為浮點數(shù)類型。