二分查找模闆題（數的範圍）題解

這是一題非常典型的二分查找資料左下界和右上界模闆題。

題目

題目連結

AcWing的網站，https://www.acwing.com/solution/acwing/content/3338/。

題目描述

給定一個按照升序排列的長度為n的整數數組，以及 q 個查詢。

對于每個查詢，傳回一個元素k的起始位置和終止位置（位置從0開始計數）。

如果數組中不存在該元素，則傳回“-1 -1”。

輸入格式

第一行包含整數n和q，表示數組長度和詢問個數。

第二行包含n個整數（均在1~10000範圍内），表示完整數組。

接下來q行，每行包含一個整數k，表示一個詢問元素。

輸出格式

共q行，每行包含兩個整數，表示所求元素的起始位置和終止位置。

如果數組中不存在該元素，則傳回“-1 -1”。

樣例輸入

6 3
1 2 2 3 3 4
3
4
5
           

樣例輸出

3 4
5 5
-1 -1
           

資料範圍

1 ≤ n ≤ 100000

1 ≤ q ≤10000

1 ≤ k ≤ 10000

分析

本題是一個标準的二分查找模闆題，查找某個數的左邊界和右邊界。

使用 STL

使用 STL 的 lower_bound() 和 upper_bound() 函數的時候，有以下幾個地方需要特别注意：

1、函數的傳回值是一個左閉右開的區間。

2、使用 lower_bound() 查找左下界的時候，要注意處理沒有找到的情況。比如有這樣的數列 [3 5 5 8 7 7 9 10 11]，我們要查找 4，得到的位置将是數列中 3 所在位置。

3、使用 upper_bound() 查找右上界的時候，要注意傳回值是左閉右開區間，意味着比實際值大一。

lower_bound

該函數介紹請參考https://blog.csdn.net/justidle/article/details/104346825。

upper_bound

該函數介紹請參考https://blog.csdn.net/justidle/article/details/104346950。

AC 參考代碼

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 1e5+6;
int a[MAXN];

int main() {
    int n, q;
    scanf("%d%d", &n, &q);

    int i;
    for (i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }

    for (i=0; i<q; i++) {
        int k;
        scanf("%d", &k);

        int pos1 = lower_bound(a, a+n, k)-a;
        int pos2 = upper_bound(a, a+n, k)-a-1;
        if (k!=a[pos1]) {
            printf("-1 -1\n");
        } else {
            printf("%d %d\n", pos1, pos2);
        }
    }

    return 0;
}
           

注意

1、上面代碼如何判斷資料 k 不存在，即使用 k!=a[pos1] 來判斷。

2、使用 upper_bound 需要多減 1，因為傳回的是左閉右開區間，也就是不包含右邊點。

自己實作函數

查找左邊界

這部分模闆代碼請參考https://blog.csdn.net/justidle/article/details/104304725。

查找右邊界

這部分模闆代碼請參考https://blog.csdn.net/justidle/article/details/104304742。

AC 參考代碼

#include <cstdio>
using namespace std;

const int MAXN = 1e5+6;
int a[MAXN] = {};

int main() {
    int n, q;
    scanf("%d%d", &n, &q);

    int i;
    for (i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }

    for (i=0; i<q; i++) {
        int k;
        scanf("%d", &k);

        //從0~n-1找左邊界
        int left = 0;
        int right = n-1;
        int mid;
        while (left<right) {
            mid = left+((right-left)>>1);
            if (a[mid]<k) {
                left = mid+1;
            } else {
                right = mid;
            }
        }
        if (a[left]!=k) {
            printf("-1 -1\n");
            continue;
        }
        printf("%d ", left);

        //left到n找右邊界
        right=n;
        while (left+1<right) {
            mid = left+((right-left)>>1);
            if (a[mid]<=k) {
                left = mid;
            } else {
                right = mid;
            }
        }
        printf("%d\n", left);
    }

    return 0;
}