(整数二分)

时间复杂度

O(logn)

JAVA 代码

import java.util.Scanner;
import java.io.BufferedInputStream;

//整数二分
class Main{
    public static final int N = 100010;
    public static int[] arr = new int[N];

    //寻找右边界点，右边界点的性质（check函数部分）如下：
    //点的左边都小于等于target
    public static int findR(int[] arr, int l, int r, int x){
        while(l < r){
            //模板
            int mid = l + r + 1 >> 1;
            if(arr[mid] <= x)
                l = mid;
            else
                r = mid - 1;
        }
        //特殊情况，输入内不包含target
        if(arr[l] != x)
            return -1;
        return l;
    }
    //寻找左边节点，点的右边都大于等于target
    public static int findL(int[] arr, int l, int r, int x){
        while(l < r){
            int mid = l + r >> 1;
            if(arr[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        if(arr[l] != x)
            return -1;
        return r;
    }
    //程序入口
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int q = in.nextInt();

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        while (q > 0) {
            int x = in.nextInt();
            int l = findL(arr, 0, n - 1, x);
            int r = findR(arr, 0, n - 1, x);
            System.out.println(l + " " + r);
            q--;
        }
    }
}