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

发布时间:2024年01月14日

二分查找

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

在这里插入图片描述

文章来源:https://blog.csdn.net/qq_42985872/article/details/135588096
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。