题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

[//]: # (打卡模板，上面预览按钮可以展示预览效果 ^^)

import java.io.*;
public class Main{

public static void main(String [] args)throws IOException{
    BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
    String str [] = re.readLine().split(" ");

    int n = Integer.parseInt(str[0]);
    int arr [] = new int [n];
    int m = Integer.parseInt(str[1]);

    str  = re.readLine().split(" ");
    for(int i = 0;i<n;i++) arr[i] = Integer.parseInt(str[i]);

    while(m-->0){
        str  = re.readLine().split(" ");
        int x = Integer.parseInt(str[0]);

        int l =0,r = n-1;//两边的边界

        while(l<r){
            int mid  = l+r>>1;//二分二分 一分为二 取中间值

            if(arr[mid]>=x)//如果mid大于x  那么答案一定在左半边  先找左边的也就是小的
                r=mid;//l~mid
            else 
                l=mid+1;//否则一定是mid+1~r
        }

        /**
        样例
        n=6
        1 2 2 3 3 4 
        l=0 r = 5
        第一次：
            0小于5
            x=3
            mid=2

            开始判断：
                arr[2] = 2;
                2不大于等于3
                所以答案一定是在mid的后面
                即把 区间更新为   mid+1~r
                l=3


        第二次

            x=3
            l=3 r=5
            3小于5
            mid = 4

                开始判断
                    arr[4] = 3;
                    3等于x
                    所以答案一定是在mid的左边 并且包括mid
                    所以把区间更新为 l~r（mid=4）
                    r=4;
        第三次

            l=3 r=4
            x=3 
            3小于4
                mid=3

            开始判断：
                arr[3]=3;
                3等于x
                 所以答案一定是在mid的左边 并且包括mid
                 所以把区间更新为 l~r（mid=3）
                r=3
        第四次
            l=3 r=3 x=3
            3不小于3

    判断arr[l]是否是x  
             不是输出-1 -1

    是输出起始位置  l或者r都可以


    右边

    l = 0;r=5 x=5；

    0小于5


    第一次：
        0小于5
         mid=3;//加1的原因是因为左边已经判断过了   
         arr[3]=3 
         等于x
            所以右边的答案 一定在mid的右边 包括mid
                所以把区间更新为
                    (mid=3)l~r
                    l=3;


    l = 3;r=5 x=5；

    第二次

        3小于5
        mid=4;
        arr[mid] = 3;

            所以右边的答案 一定在mid的右边 包括mid
                所以把区间更新为
                    (mid=4)l~r
                    l=4;

    l = 4;r=5 x=5；

    第三次
        4小于5
        mid = 5；
        arr[5]=4;
        4大于3
        答案一定是在mid的左边  因为是绝对大于 不包括mid
        所以更新为
            l~r(mid5-1)  4~4


    第四次：
        4不小于

        输出l或者r






         */

        if(arr[l]!=x)
            System.out.println("-1 -1");
        else {

            System.out.print(l + " ");
             l  = 0;  r = n-1;


            while(l<r){

                int mid = l+r + 1>>1 ;

               if(arr[mid]<=x)//如果mid小于等于x  那么答案一定在右半边
                    l  = mid;
                 else r =mid-1;
            }
            System.out.println(l + " ");
        }


    }

}

}