题目描述

找一组数的起始坐标和终止坐标,没有的话返回-1 -1

样例

输入

6 3
1 2 2 3 3 4
3
4
5

输出

3 4
5 5
-1 -1

解题思路—二分查找

主要用到了用到了两个模板，一个找左边界（r=mid），一个找有边界（l=mid）的模板。主要思想就是不断折半查找。

时间复杂度：$O(nlogn)$

参考文献：y总

JAVA 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static int[] arr = new int[100010];
    public static int bsearch_01(int l, int r, int k){
        if (l > r) return 0;

        while (l < r){
            int mid = (r + l) / 2;
            if (arr[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if (arr[l] != k) return -1;
        return l;
    }

    public static int bsearch_02(int l, int r, int k){
        if (l > r) return 0;

        while (l < r){
            int mid = (r + l + 1) / 2;
            if (arr[mid] <= k) l = mid;
            else r = mid - 1;
        }
        if (arr[l] != k) return -1;
        return l;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        String[] str_01 = scan.readLine().split(" ");
        int m, n;
        m = Integer.parseInt(str_01[0]);
        n = Integer.parseInt(str_01[1]);

        String[] str_02 = scan.readLine().split(" ");
        for (int i = 0; i < m; i++){
            arr[i] = Integer.parseInt(str_02[i]);
        }

        int[] cc = new int[n];
        for (int i = 0; i < n; i++){
            cc[i] = Integer.parseInt(scan.readLine());
        }

        for(int k : cc){
            System.out.println(bsearch_01(0, m - 1, k) + " " + bsearch_02(0, m - 1, k));
        }
    }
}

坑位

1. while (l < r) 循环退出条件是不能让l==r的，如果相等则会进入死循环
2. 如果控制台一直能输出说明调用的方法可能是一个死循环