//    二分及应用
public class d1 {

//    二分
    public static int getindex(int[]arr,int num){
        int l=0;
        int r=arr.length-1;
        while(l<=r){
            int mid=(l+(r-l)>>1);
            int temp=arr[mid];
            if(temp>num){
                r=mid-1;
            }else if(temp<num){
                l=mid+1;
            }else{
                return mid;
            }
        }
        return -1;//-1表示没有找到
    }

//    在一个arr上面找 >=num最左边的位置
    public static int getleftindex(int[]arr,int num){
        int l=0;
        int r=arr.length-1;
        int result=-1;//-1表示没有找到
        while(l<=r){
            int mid=(l+(r-l)>>1);
            int temp=arr[mid];
            if(temp>=num){
                r=mid-1;
                result=mid;
            }else{
                l=mid+1;
            }
        }
        return result;
    }

    //    在一个arr上面找 <=num最右边的位置
    public static int getrightindex(int[]arr,int num){
        int l=0;
        int r=arr.length-1;
        int result=-1;//-1表示没有找到
        while(l<=r){
            int mid=(l+(r-l)>>1);
            int temp=arr[mid];
            if(temp<=num){
                l=mid+1;
                result=mid;
            }else{
                r=mid-1;
            }
        }
        return result;
    }

}