二分法模板

数组具有二段性，可以分为左右两边合法区和不合法区

如果选择左端点，右边区域不合法，选择 left = mid ,right = mid - 1;

如果选择右端点，左边区域不合法，选择 left = mid + 1 ,right = mid ;

 1.x 的平方根 

LCR 072. x 的平方根 - 力扣（LeetCode）

class Solution {
    public int mySqrt(int x) {
        // 边界情况处理：如果 x 小于 1，直接返回 0
        if (x < 1) return 0;

        // 使用 long 类型避免 mid * mid 溢出
        long mid = 0;
        long left = 1;       // 搜索范围的左边界
        long right = x;      // 搜索范围的右边界

        // 二分查找
        while (left < right) {
            // 计算中间值，+1 是为了避免死循环
            mid = left + (right - left + 1) / 2;

            // 检查 mid 的平方是否小于等于 x
            if (mid * mid <= x) {
                // 如果 mid 的平方小于等于 x，说明平方根在右半部分或 mid 就是平方根
                left = mid;  // 更新左边界
            } else {
                // 如果 mid 的平方大于 x，说明平方根在左半部分
                right = mid - 1;  // 更新右边界
            }
        }

        // 返回平方根的整数部分，将 long 类型强制转换为 int
        return (int) left;
    }
}

2. 搜索插入位置

 考虑小于/等于/大于时目标值的时候放在哪里。

class Solution {
    public int mySqrt(int x) {
        //选择左端点，右边是非法区，right = mid - 1;
        if(x < 1) return 0;

        long mid = 0;
        long left = 1;
        long right = x;
        while(left < right){
            mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return (int) left;
    }
}

 3.山脉数组的峰顶索引

 该题具有二段性，左边升序为一段，右边降序为一段。

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid]> arr[mid-1]) left = mid;
            else right = mid - 1;
        }
        return left;
        
    }
}

4.寻找峰值

 可以分为两段性

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]) right = mid;//去左区间寻找，right指针移动
            else left = mid + 1;//去右区间寻找，left指针移动
        }
        return left;
        
    }
}

5.寻找旋转排序数组中的最小值 

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int x = nums[right];//标记最后一个元素

        while(left < right){
            int mid = left + (right - left ) / 2;
            if(nums[mid] > x) left = mid + 1;
            else right = mid;
        }
        return nums[left];
        
    }
}

6.点名 

class Solution {
    public int takeAttendance(int[] records) {
        //1.二分算法
        int left = 0;
        int right = records.length - 1;
        int mid = 0;
        while(left < right){
            mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        //边界问题
        if(records[left] == left) return left + 1;
        else return left;
        
    }
}