1.思路(二分查找分为查找左边界和右边界)

a为要查找的数组，x为数组要查找的数，要求要查找x的左右边界

查找左边界，也就是从左往右找到的第一个不小于x的数

①确定分界点mid，mid为区间的中点mid=l + r >> 1;

②判断a[mid]是否小于x，小于则代表答案在右边且不包含mid这个点，否则就代表答案在左边且包含mid这个点

③继续下一次查找，直到l >= r，跳出循环

查找右边界，也就是从左往右找到的第一个不大于x的数

①确定分界点mid，mid为区间的中点 mid = l + r + 1 >> 1;（加1为了防止死循环）

②判断a[mid]是否小于等于x，小于等于则代表答案在右边且包含mid这个点，否则就代表答案在左边且不包含mid这个点

③继续下一次查找，直到l >= r，跳出循环

2.代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = in.nextInt();
        while(q --> 0) {
            int x = in.nextInt();
            int l = 0, r = n - 1;
            while(l < r) {
                int mid = l + r >> 1;
                if (a[mid] < x)  
                    l = mid + 1;    //代表答案在右边且不包含mid这个点
                else    
                    r = mid;        //代表答案在左边且包含mid这个点
            }
            int left = r;
            if(a[left] != x)        //如果x在数组不存在
                System.out.println("-1 -1");
            else {
                l = 0;
                r = n - 1;
                while(l < r) {
                    int mid = l + r + 1 >> 1;   //加1为了防止死循环
                    if (a[mid] <= x) 
                        l = mid;                //代表答案在右边且包含mid这个点
                    else 
                        r = mid - 1;            //代表答案在左边且不包含mid这个点
                }
                System.out.println(left + " " + r);
            }
        }
    }

}

3.复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

4.注意

左边界模板很容易理解，但是右边界模板还时要注意一下死循环问题，mid记得加一。