C++二分查找邊界

查找左邊界

Question

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

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

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

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

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

binary_search_edge.cpp

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

查找右邊界

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

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

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

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

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

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

binary_search_edge.cpp

/* 二分查找最右一個(gè) target */
int binarySearchRightEdge(vector<int> &nums, int target) {
    // 轉(zhuǎn)化為查找最左一個(gè) target + 1
    int i = binarySearchInsertion(nums, target + 1);
    // j 指向最右一個(gè) target ，i 指向首個(gè)大于 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 時(shí)，最終 i 和 j 會(huì)分別指向首個(gè)大于、小于 target 的元素。

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

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

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

代碼在此省略，值得注意以下兩點(diǎn)。

• 給定數(shù)組不包含小數(shù)，這意味著我們無(wú)須關(guān)心如何處理相等的情況。
• 因?yàn)樵摲椒ㄒ肓诵?shù)，所以需要將函數(shù)中的變量 target 改為浮點(diǎn)數(shù)類型。