【xsong 说算法】第二期:二分查找算法

本贴最后更新于 1082 天前,其中的信息可能已经时异事殊

前言

别直接背模板,要理解记忆

  • 二分查找的基本思想:[ 减而治之 ] 每次都将问题的规模减少,直到问题解决

”开胃菜“LeetCode 1095 山脉数组中查找目标值

重点:二分查找两种思路:

  • 思路 1:在循环体内部查找元素:while (left <= right)
  • 思路 2:在循环体内部排除元素:while (left < right)

关于二分查找我想说

  1. 防止整型溢出求中点的写法:mid = left + (right - left) / 2

  2. 二分查找类问题中上取整和下取整的问题。这里我给大家举个例子:给一个数组 [1 ,2] 正常来说我们求中点位置的计算方法是 mid = (left + right)/ 2,这样计算得到的中点位置的下标是 0 对应上面数组中的 1 ,这是向下取整,当我们见到 left = mid 的时候,这时候我们都是使用向上取整,也就是 mid = (left + right + 1)/ 2 这种写法,因为只有这样我们的 mid 才能落在后面。具体细节建议大家 debug 去分析。

  3. 每次做完判断就要明确自己的下一步落点区间实在什么位置,不要死记硬背模板!

  4. 二分查找中,我们常见的数组是升序 ,并且元素是不重复的,但是我们同样会遇到那种元素重复的题。例如:LeetCode 81. 搜索旋转排序数组 IILeetCode 154. 寻找旋转排序数组中的最小值 II 里面给的数组虽然是升序或者降序排序,但是里面的元素是重复的,这时候我们就要去重,这里给大家一个简单的去重方法,大家只需要在之前的判断基础上加上以下代码 👇👇👇👇

    if(nums[left] == nums[mid] && nums[mid] == nums[right]) {
       ++left;
       --right;
    }
    
    • 在二分查找这一章节中,我给大家的建议是多刷题,弄清楚每一步的原因。
    • 二分查找题我个人认为是细节魔鬼,搞懂其中的细节,二分查找题不在话下!

LeetCode 二分查找类型

704. 二分查找

题目链接

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

[力扣] 1095. 山脉数组中查找目标值

题目链接

我的题解

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

题目链接

我的题解

33. 搜索旋转排序数组

题目链接

我的题解

81. 搜索旋转排序数组 II

题目链接

我的题解

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

题目链接

我的题解

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

题目链接

我的题解

69. Sqrt(x)

题目链接

我的题解

658. 找到 K 个最接近的元素

题目链接

  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • function001

    点赞 +1,投币 +1,收藏 +1