二分- 二分找的是边界状态

时间复杂度 logN

java代码

import java.io.*; // 输入输出

class Main{
    public static int[] solution(int[] q, int x) {
        int l = 0, r = q.length - 1;
        int[] ans = new int[2];
        while (l < r) {
            int mid = (l + r) / 2;
            if (q[mid] >= x) { // 第一个大于等于x的
                r = mid;
            } else l = mid + 1;
        }
        if (q[r] == x) ans[0] = r;
        else ans[0] = -1;
        l = 0;
        r = q.length - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (q[mid] <= x) { // 最后一个小于等于x的
                l = mid;
            } else r = mid - 1;
        }
        if (q[r] == x) ans[1] = r;
        else ans[1] = -1;
        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        args = br.readLine().split(" ");
        int n = Integer.valueOf(args[0]);
        int k = Integer.valueOf(args[1]);

        int[] q = new int[n];
        args = br.readLine().split(" ");
        for (int i = 0; i < n; ++i) {
            q[i] = Integer.valueOf(args[i]); 
        }

        for (int i = 0; i < k; ++i) {
            int x = Integer.valueOf(br.readLine());
            int[] ans = solution(q, x);
            System.out.println(ans[0] + " " + ans[1]);
        }

    }
}