【算法练习】leetcode算法题合集之二分查找篇

二分查找

LeetCode69.x的平方根

LeetCode69.x的平方根

只要小于等于就可以满足条件了。

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;
        int ans = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if ((long) mid * mid <= x) {
                ans = mid;
                left = mid + 1;

            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

LeetCode34.在排序数组中查找元素的第一个和最后一个位置

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

二分查找获取元素的左边界

左边界是可能不存在的。

当target==nums[mid]，继续在左边寻找更合适的mid

class Solution_LC34 {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBounds(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        int end = lowerBounds(nums, target + 1) - 1;
        return new int[]{start, end};
    }

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

二维矩阵类

LeetCode74.搜索二维矩阵（??高频）

LeetCode74.搜索二维矩阵

LeetCode240.搜索二维矩阵II

这道题虽然不是用传统的二分模板来做的，但是里面的思想其实还是上面二分模板的思想，一次次的排除不可能的区域，最后剩下的要么是最终的答案要么没有答案。

LeetCode240.搜索二维矩阵II