二分法

69. x 的平方根

class Solution {
    public int mySqrt(int x) {
       //1.判断l r区间
        int l = 0, r = x;
        
        //二分框架
        while(l < r){
            int mid = l + r +1 >> 1;
            
            //二分性质
            if(mid <= x / mid)
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }
}

数的范围

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
            
        while(m-- >0){
            int x;
            x = sc.nextInt();
            
            int l = 0, r = n -1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(arr[mid] >= x) r = mid;
                else l = mid +1;
            }
            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) l = mid;
                    else r = mid - 1;
                }
                System.out.println(l);
            }
            
        }
            
    }
}