Java 算法：二分查找核心原理与经典例题

练习一 : 二分查找

704. 二分查找 - 力扣（LeetCode）

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2; // 防止溢出
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else { // nums[mid] < target
                left = mid + 1;
            }
        }
        return -1;
    }
}

算法原理

1. 数组必须有序
2. 每次取中间位置，和目标值比较
3. 比目标小 -> 去右边找
4. 比目标大 -> 去左边找
5. 直到找到或找不到

⭐⭐⭐ 练习二 : 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len - 1;
        int mid = 0;
        int[] ret = {-1, -1};
        
        if (len == 0 || nums[len - 1] < target || nums[0] > target) {
            return ret;
        }
        
        // 找左端点
        int retLeft = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            // 找左端点时，如果存在则最后 mid 会落在 left 处，经过处理会让两个指针重合，退出循环，返回结果
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 判断双指针重合处是否是端点
        if (nums[left] != target) {
            return ret;
        }
        retLeft = left;
        
        // 找右端点
        int retRight = 0;
        left = 0;
        right = len - 1; // 记得恢复指针
        while (left < right) {
            mid = left + (right - left + 1) / 2;
            // 找右端点时，如果存在则最后 mid 会落在 right 处，经过处理会让 left 和 right 重合，退出循环，返回结果
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        retRight = right;
        
        // 经过找左端点后如果进入到寻找右端点，则数组中一定包含 target，此时不需要进行判断
        ret[0] = retLeft;
        ret[1] = retRight;
        return ret;
    }
}

算法原理

找左端点 :

• 当 mid 落在 < target 处，要让 left 跳出非法区域 (left = mid + 1)
• 当 mid 落在 >= target 处，要让 right 移到 mid 处 (right = mid)，因为不能保证 mid - 1 和 mid 处是否是左端点
• 当退出本次循环时，还需要判断一下双指针重合位置是否是 target

找右端点 :

• 和找左端点同理；当 mid 落在 <= target 处，要让 left 移到 mid 处 (left = mid)，因为不能保证 mid + 1 和 mid 处是右端点
• 当 mid 落在 > target 处，要让 right 跳出非法区域 (right = mid - 1)
• 能进入此次循环，意味着数组中一定包含 target，所以不需要判断双指针位置的合法性 (即使数组中只有一个 target)

注意

1. 循环条件 : left < right

   因为只有当两指针重合时 (right == left)，才能退出循环，判断合法性；如果写成 left <= right，则最后一步 right == left == mid 时会一直死循环

2. mid 处理过程 (防止溢出和死循环)

   找左端点 → 用「左中位数」：mid = left + (right - left) / 2

   找右端点 → 用「右中位数」：mid = left + (right - left + 1) / 2

   左中数 : 处理后 mid 会更靠近 left，直到等于 left；目的是让 right 主动向左收敛，最终重合

   右中数 : 处理后 mid 会更靠近 right，直到等于 right；目的是让 left 主动向右收敛，最终重合

核心模板

练习三 : 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

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

练习四 : x 的平方根

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

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int left = 1, right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == x / mid) return mid;
            else if (mid > x / mid) right = mid - 1;
            else left = mid + 1;
        }
        return right;
    }
}