题目

https://www.acwing.com/problem/content/791/

算法思想

本题目是一道经典的整数二分题目，二分要求数组本身具有有序性或者类似于有序的性质，其本质是在左区间或者右区间找到满足某个性质的边界点。如下图所示

左区间

右区间

以该题目为例，数组本身是单调递增的，因此满足二分的前提条件。其次，我们需要找到元素 k 的起始位置和终止位置，对于起始位置来说，需要满足右区间 >= k，每次得到 arr[mid] >= k 时, r = mid，相反 arr[mid] < k 时，l = mid + 1；对于终止位置来说，需要满足左区间 <= k，每次得到 arr[mid] <= k 时，l = mid，相反 arr[mid] > k 时，r = mid - 1。

注意：对于二分来说，循环一定会终止，但是终止之后边界点是否满足我们的需求，需要进行判断。

解法

#include <cstdio>

const int N = 100010;

int arr[N];

int main() {
    int n, q, k, l, r, mid;
    scanf("%d%d", &n, &q);
    
    for(size_t i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
        
    while(q--) {
        scanf("%d", &k);
        l = 0, r = n - 1;
        while(l < r) {
            mid = l + ((r - l) >> 1);
            if(arr[mid] >= k) r = mid;
            else l = mid + 1;
        }
        
        if(arr[l] != k) { puts("-1 -1"); }
        else {
            printf("%d ", l);
            
            l = 0, r = n - 1;
            while(l < r) {
                mid = l + ((r - l + 1) >> 1);
                if(arr[mid] <= k) l = mid;
                else 
                    r = mid - 1;
            }
            
            printf("%d\n", l);
        }
    }
    
    return 0;
}

为什么在左边界的情况下，我们需要 +1，这是因为当 l = r - 1 的时候，mid 向下取整，会等于 l，如果 arr[mid] <= k，就永远不会更新，因此陷入死循环。

复杂度

时间复杂度：log(n)，空间复杂度：O(1)。