当前位置: 首页 > article >正文

优选算法的匠心之艺:二分查找专题(一)

专栏:算法的魔法世界

个人主页:手握风云

目录

一、二分查找算法

二、例题讲解

2.1. 二分查找

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

2.3. x 的平方根

2.4. 搜索插入位置


一、二分查找算法

        可能很多老铁在之前可能接触过朴素的二分查找思想,比如在一个有序数组中找到目标值。但二分查找算法不仅仅局限于数组有序的场景下,只要一个数组里面符合“二段性”,当数组中间的某一个值不符合要求,我们就可以把这个值左区间或者右区间舍去,再去另一个区间进行查找。这个“二段性”,并不一定从中间划分,也可以1/3、1/4出开始划分。但我们大部分还是选择从中间划分,因为从概率学角度讲,中间划分是数学期望最高的。二分查找算法细节特别多,也特别容易写出死循环。但我们要理解了算法原理和二分查找的模板,那么就非常简单了。

二、例题讲解

2.1. 二分查找

        对于上面的题,我们可以先使用暴力解法,利用for循环遍历数组中的每一个元素来找到目标值,这个算法的时间复杂度为O(n)=n

class Solution {
    public int search(int[] nums, int target) {
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }
}

        接下来对这个算法进行优化,我们先设x = (right + left)/2。如果nums[x] > target,那么left = x+1;如果nums[x] < target,那么right = x-1;如果nums[x] = target,直接返回x,循环走下来找不到,返回-1。

        有些细节我们需要注意一下:1.循环结束的条件是什么?当x与目标值进行比较时,left可以移动到x右边,那么x的左边已经判断过了都是小于目标值,但右边还是未知的,即使left与right相遇,那这个数依然是未知的。所以循环结束的条件是left>right,而不是left==right。2.为什么二分查找是正确的?二分查找虽然不像上面的暴力解法一个一个比较,但我们利用“二段性”以及数组的有序性,只比较一个数字就排除一半的区间。3.二分查找的时间复杂度。当我们的循环执行一次时,将区间划分为\frac{n}{2};循环执行两次时将区间划分为\frac{n}{4};循环执行三次时将区间划分为\frac{n}{8}……最坏情况下left与right相遇,将区间划分为1,则\frac{n}{2^{x}}=1,时间复杂度为O(n)=logn

        完整代码实现:

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

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

        我们的暴力解法,就是去从前往后遍历数组,找出起始位置用begin记录,然后找出结束位置用end记录,最终返回[begin,end]。很明显,暴力解法的时间复杂度为O(n) =n

        我们还是根据数组有序的特性,来利用二分查找进行优化。这里我们不能使用上面的朴素二分查找,因为找出的中间值无法确定是不是起始位置或者结束位置,我们向左和向右遍历数组找出起始与结束,所以时间复杂度依然是O(n) =n。所以朴素的二分查找不能解决问题。

        我们还是要回归到二分查找的本质,“二段性”。我们先来查找区间的左端点,我们假设中间下标mid对应值的值为x,让x与target进行比较。如果x小于target,说明mid位于左边的区间,让left = mid+1;如果x大于等于target(这里等于的时候,并不一定是最终位置),说明mid位于右边的区间,让right=mid(因为mid指向的位置有可能正好是左区间)。

        我们需要处理一下细节:1.循环条件。right指针移动的时候,一直是在合法的区间,left一直想要跳出这个不合法的区间,直到两个指针相遇,无需判断,相遇的位置就是我们要找的结果。并且如果left=right,一直处于x>=t的条件,而right指针又不会移动,就会陷入死循环。

        2.找出中点操作。中点有两种求法,mid=left+(right-left)/2或者是mid=left+(right-left+1)/2。如果数组元素个数为偶数个,按照第二种求法,mid就会落在右边,又会陷入死循环,所以我们需要选择第一种求法。

        接下来是查找区间的右端点,与上面的查找左端点的方法大同小异,只是细节的处理不一样。我们要划分的区间为小于等于target与大于tareget两部分,求中点的方式要采用第二种,防止mid落在左边的元素造成死循环。

        完整代码实现:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;

        //处理边界情况
        if (nums.length == 0) return ret;

        //查找左端点
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        //判断是否有结果
        if (nums[left] != target) return ret;
        else ret[0] = right;

        //二分右端点
        left = 0;
        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        ret[1] = left;
        return ret;
    }
}

        模板总结:

//查找左端点
while (left < right) {
    int mid = left + (right - left) / 2;
    if (……) left = mid + 1;
    else right = mid;
}

//查找右端点
while (left < right) {
    int mid = left + (right - left + 1) / 2;
    if (……) left = mid;
    else right = mid - 1;
}

2.3. x 的平方根

        题目要求不适用内置函数求平方根,我们需要自己写一个算法来求平方根。如果求出的平方根是小数,则舍去小数部分。

        我们先来思考暴力解法:由于x是非负整数,那么x的平方根定义是小于等于x的。其中0和1的平方根都为它本身。如果x=17,我们可以从1开始向右枚举,如果找到一个数n,n*n小于等于x,且(n+1)*(n+1)大于x,则x的平方根则为n。

        我们可以直接套用上面的模板。如果mid * mid <= x,则left=mid; 如果mid * mid > x,则right=mid+1。这里还有一点需要注意,mid*mid可能会因为数据太大造成溢出,所以mid用long来创建。

        完整代码实现:

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

2.4. 搜索插入位置

        通过上面的示例分析,插入结果分为两种:1.插入第一个大于等于target前的位置;2.插入数组的末尾。很明显,我们可以按照查找区间左端点的模板来解决。我们还需要判断一下示例3这种情况,也就是插入数组的末尾。

        完整代码实现:

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

http://www.kler.cn/a/585233.html

相关文章:

  • 微前端解决方案之MicroApp
  • 基于YOLO11深度学习的舌苔舌象检测识别与诊断系统【python源码+Pyqt5界面+数据集+训练代码】
  • OpenCV特征提取与深度学习CNN特征提取差异
  • 58.Harmonyos NEXT 图片预览组件架构设计与实现原理
  • 【Idea】 xml 文本粘贴保持原有文本的缩进格式
  • C语言的机器学习
  • C++ STL 深度解析:vector 的全面指南与进阶技巧
  • Java 实现定长报文模拟器(支持配置文件 默认值)
  • 计算机网络TCP/IP四层模型
  • 列表动态列处理
  • 链表与栈的实现及操作详解:从基础到应用
  • GIT日常记录
  • 六十天前端强化训练之第十五天React组件基础案例:创建函数式组件展示用户信息(第15-21天:前端框架(React))
  • ES怎么通过客户端操作和查询/curl操作指令
  • 地下停车场调频广播覆盖:破解地下车库无线广播收听孤岛,技术赋能地下停车场FM调频无线广播覆盖
  • 【python实战】-- 选择解压汇总mode进行数据汇总20250314更新
  • 61.Harmonyos NEXT 图片预览组件之数据模型设计与实现
  • API自动化测试实战:Postman + Newman/Pytest的深度解析
  • 注意力机制,层归一化,RBA。KAN-ODE,小波KAN
  • 如何使用Postman,通过Mock的方式测试我们的API