首页 > 编程语言 >二分查找算法:朴素二分+左右边界二分&力扣实战应用

二分查找算法:朴素二分+左右边界二分&力扣实战应用

时间:2024-08-27 12:26:00浏览次数:14  
标签:二分 right int mid 力扣 算法 查找 left

目录:

1、二分查找算法简介

2、算法原理及时间复杂度分析

2.1 朴素二分算法

3.2 查找左右边界的二分算法

3.2.1 查找左边界

3.2.2 查找右边界

3.3 时间复杂度分析

3、二分查找算法模版

3.1 朴素二分模版

3.2 查找左右边界的二分模版

4、算法应用【leetcode】

4.1 题一:搜素插入位置

4.1.1 思路分析

4.1.2 算法代码

4.2 题二:x的平方根

4.2.1 思路分析

4.2.2 算法代码

4.3 题三:山峰数组的峰顶索引

4.3.1 思路分析

4.3.2 算法代码

4.4 题四:寻找峰值

4.4.1 思路分析

4.4.2 算法代码

4.5 题五:寻找旋转排序数组中的最小值

4.5.1 思路分析

4.5.2 算法代码

4.6 题六:点名 (原:剑指Offer:0~n-1 中缺失的数字 )

 4.6.1 思路分析

4.6.2 算法代码


1、二分查找算法简介

算法,是一种思想,并不是固定的模式,我们可以使用一种算法思想解决多种问题。

二分查找算法,是一个细节最多、最恶心、最容易写出死循环的一个算法,但是当我们熟练掌握后它就可以变成一个最简单的算法,利用它,仅仅使用十几行代码就可以解决掉一个难题,所以在算法学习的路途中,二分查找算法的学习是极为重要且必不可少的。

二分法查找算法的使用条件:数据具有“二段性”。(并非数据有序)

注意:并不是只有数据有序的情况下才可以使用二分查找算法,只要数据具有二段性,即使数据乱序,也可以使用二分查找算法!!!

2、算法原理及时间复杂度分析

这里通过例题为大家讲解算法原理。

2.1 朴素二分算法

. - 力扣(LeetCode)

使用二分查找算法的关键点是:数据具有“二段性”。

因为数组为升序排列,所以target左边的数据均<target,target右边的数据均>target,故可将数据分为“二段”,具有二段性,可以使用二分查找算法。

定义left和right指针分别指向数组0下标处和nums.length-1处,以及定义他们的中间位置mid,将nums[mid]和target比较,

  1. nums[mid] < target ---> left = mid+1;
  2. nums[mid] > target ---> right = mid-1;
  3. nums[mid] == target ---> 返回结果;

这样一次比较即可过滤掉一半数据,大大提高了查找效率。、

注意:

  • 循环条件为:left <= right
  • 为防止数据溢出,更新mid的方式为:mid = left + (right - left) / 2;或者mid = left + (right - left + 1) / 2;

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

注意:朴素二分算法因为太过简单,所以基本不会考察,重点是下方的边界二分查找算法的思想。


3.2 查找左右边界的二分算法

. - 力扣(LeetCode)

因为数组为非递减排序,也就是说数据要么相等,要么递增,而我们要找的就是相等数据target的开始和结束位置。

也就是说,我们要找到target的左边界位置和右边界位置,而target的左边的数据小于target,右边的数据大于target,数据同样具有二段性,可以使用二分查找算法。

同样定义left和right指针,定义mid指向他们的中间位置。

3.2.1 查找左边界

  1. 循环条件为:left < right,left == right时就是最终结果,结束循环
  2. nums[mid] < target ---> left = mid+1;//mid的位置肯定不为左边界,所以left = mid+1
  3. num[mid] >= target ---> right = mid;//mid的位置可能就是左边界,所以right=mid
  4. 更新mid:mid = left + (right - left) / 2;

3.2.2 查找右边界

  1. 循环条件为:left < right,left == right时就是最终结果,结束循环
  2. nums[mid] <= target ---> left = mid;//mid的位置可能就是右边界,所以left=mid
  3. nums[mid] > target ---> right = mid-1;//mid的位置肯定不为右边界,所以right= mid-1
  4. 更新mid:mid = left + (right - left + 1) / 2;因为更新right或left时,有-1操作,所以这里更新mid要+1(技巧,记忆即可)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] arr = new int[]{-1,-1};
        //nums为空数组
        if (nums.length == 0) return arr;
        //查找左边界
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        //数组中不存在target
        if (nums[left] != target) return arr;
        arr[0] = left;
        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;
            }
        }
        arr[1] = left;
        return arr;
    }
}

注意:

  • 朴素二分算法的循环条件是:left <= right;因为要查找的数据可能就在left和right重叠的位置处。
  • 边界二分算法的循环条件是:left < right;因为当left == right时,就是最终结果。
  • 为避免数据溢出:mid = left + (right - left) / 2 或者 mid = left + (right - left + 1) / 2,朴素算法+1与否都可以,但是在找边界的二分算法中,若更新left或者right时,有-1出现,则更新的mid要+1。

3.3 时间复杂度分析

第一次二分查找剩下n/2个数据,第二次二分查找剩下n/4个数据,第三次二分查找升序n/8个数据,直至最后一次(第x次)二分查找剩下1个数据(此时查找成功),则n/2^{x} == 1,计算得x == logN,因为x就是循环执行的次数,故二分查找算法时间复杂度为:O(logN)

大家可能觉得O(logN)对于O(N)的提升不是很大,其实并不是这样,举个例子:

假设存储了2^{32}个数据,若用O(N)的算法去查找某一个数据,即遍历所有数据,那么最多需要查找2^{32}=4,294,967,296次;而使用O(logN)的算法,则最多查找32次就可以查找成功。

综上所述,O(logN)相对于O(N)的提升非常的大,故二分查找算法是一个极为高效的算法,每次都能排除掉一半的数据,从而快速定位到目标位置。

3、二分查找算法模版

对于算法的模版,一定不要死记硬背,要理解后再记忆,这样才可以在不同的题目中灵活使用该算法。

3.1 朴素二分模版

朴素二分模版是最简单的二分模版,因为简单,所以也很少考察。

注意:朴素模版中的循环条件为: left <= right

//朴素二分模版
        while (left <= right) {
            int mid = left + (right - left) / 2;//避免数据溢出
            //int mid = left + (right - left + 1) / 2;在朴素二分中,加不加1均可
            if(....) {
                left = mid+1;
            } else if (....) {
                right = mid-1;
            }else {
                return ....;
            }
        }

3.2 查找左右边界的二分模版

注意:边界模版中的循环条件为: left < right


4、算法应用【leetcode】

4.1 题一:搜素插入位置

. - 力扣(LeetCode)

4.1.1 思路分析

分析数据,可以发现target要插入的位置就是第一个比target大的数据的位置,而这个位置左侧的均小于target,右侧的数据均大于target,故具有二段性,可以使用二分查找算法。

而我们的目的就是:找到第一个大于target的数据的位置,返回这个位置的下标即可。

需要注意一个边界情况:当target比所以数据都大时,也就是说target要插入数组的末尾,需要特殊处理。

4.1.2 算法代码

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

4.2 题二:x的平方根

. - 力扣(LeetCode)

4.2.1 思路分析

分析数据,因为目标数据的平方是 小于或等于 x的,所以目标数据及其左侧数据(包括目标数据)的平方均小于等于x,右侧数据的平方均大于x。故具有二段性,可使用二分查找算法解决该题。

4.2.2 算法代码

class Solution {
    public int mySqrt(int x) {
        long left = 0;
        long right = x;
        while (left < right) {
            //mid*mid 可能超出范围,定义为long长整型
            long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return (int)left;
    }
}

4.3 题三:山峰数组的峰顶索引

. - 力扣(LeetCode)

4.3.1 思路分析

由题意可知,数组一定为山峰,故峰顶左侧的数据一定小于峰顶值,峰顶右侧的数据一定大于峰顶值,故数据具有二段性,可使用二分查找算法。且题目已说明使用O(logN)的算法,故必须使用二分查找算法。

算法思想很简单:

  1. 若arr[mid] > arr[mid-1],则峰顶一定在mid右侧或峰顶就为mid;//left = mid
  2. 若arr[mid] < arr[mid-1],则峰顶一定在mid左侧;//right = mid-1

4.3.2 算法代码

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

4.4 题四:寻找峰值

. - 力扣(LeetCode)

4.4.1 思路分析

该题思路与上一题山峰数组的解题思路是一模一样的,只不过可能存在多个山峰,也就是说数组是完全无序的,所以,二分查找算法的使用并不局限于有序数组,只要数据具有二段性,就可以使用二分查找算法。

  1. 将中间值arr[mid]与arr[mid-1]比较,若arr[mid] < arr[mid-1],说明在左侧一定有峰值,而右侧是不确定的,可能有也可能没有,这样就可以过滤掉右侧数据,在左侧数据继续寻找山峰;
  2. 同样,若arr[mid] > arr[mid-1],说明右侧一定有山峰,而左侧不确定,过滤左侧数据,故发现数据具有二段性,能够使用二分查找算法。
  3. 因为 nums[-1] = nums[n] = -∞,所以即使数组为递增或递减序列时,也能够正确查找到峰值的位置。

4.4.2 算法代码

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

4.5 题五:寻找旋转排序数组中的最小值

. - 力扣(LeetCode)

4.5.1 思路分析

因为数组原来是升序排列,所以经过旋转,数值大的元素就移动到了数组的前面部分。

所以:

  1. 未经过旋转的元素必然小于等于数组的最后一个元素。
  2. 而经过旋转的元素必然大于数组的最后一个元素。
  3. 故数据具有二段性,可以使用二分查找算法。

因为我们是和数组的最后一个元素比较,所以即使在数组完全旋转的特殊情况下也可以得到正确结果。 

而如果是和数组的第一个元素比较的话,在特殊情况时,还需特殊处理,这种解法留给大家,可以锻炼大家的代码能力以及加强对二分查找算法的理解。

 4.5.2 算法代码

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

4.6 题六:点名 (原:剑指Offer:0~n-1 中缺失的数字 )

 . - 力扣(LeetCode)

 4.6.1 思路分析

  1. 在数组中,缺失的数字前的数据其值与其下标是相对应的。
  2. 缺失的数字后的数据其值都比其下标大1,故数据具有二段性,可以使用二分查找算法。
  3. 第一个数值与下标不对应的数据的位置,就是缺失的数据。

特殊情况:缺的是最后一个数据时,数组中的所有数据与其下标均对应,此时需要特殊处理。

4.6.2 算法代码

class Solution {
    public int takeAttendance(int[] records) {
        int left = 0;
        int right = records.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] > mid) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return records[left] == left ? left + 1 : left;
    }
}

END

标签:二分,right,int,mid,力扣,算法,查找,left
From: https://blog.csdn.net/2401_83595513/article/details/141497918

相关文章

  • 用哈希表求解力扣第217题 存在重复元素
    前言记录一下刷题历程力扣第217题存在重复元素两数之和原题目:给你一个整数数组nums。如果任一值在数组中出现至少两次,返回true;如果数组中每个元素互不相同,返回false。示例1:输入:nums=[1,2,3,1]输出:true示例2:输入:nums=[1,2,3,4]输出:false示例3:输......
  • 程序员必备的的5个刷题网站。大厂面试稳了 力扣 https://leetcode.cn
    程序员必备的的5个刷题网站。大厂面试稳了力扣https://leetcode.cn1、leetcode力扣。网址:https://leetcode.cnLeetCode是一个定位为求职的刷题网站,其中又以算法题为主。很多大厂在面试的时候,都会考算法。有空就刷一刷这里面的算法题,你的算法水平肯定会有大幅的提升,不管是求职,......
  • 浅谈二分算法
    浅谈二分算法二分首先知道一下二分是什么。二分,是一种快速处理大型数据的方法。基本逻辑是折半查找。设有一个共有\(n\)个数字的数组,要从中查询某个元素,就可以用二分查找。注:这里的数组默认其成员数值具有单调性。这个点十分重要。还记得小时候(我现在才新初一)跟同学玩过一......
  • 8.26下午二分与深搜测试
    8.26下午二分与深搜测试比赛传送门分数情况P2249【深基13.例1】查找P1706全排列问题P8647[蓝桥杯2017省AB]分巧克力P2440木材加工B3624猫粮规划P2105K皇后P3853路标设置P3743小鸟的设备01001210000015T1.P2249【深基13.例1】查找题......
  • ArrayList遍历, 元素查找
    1,ArrayList集合的遍历与数组类似,都可以使用foreach语句string[]str1={"a","b","c","d","e","f"};ArrayListList=newArrayList(str1);foreach(variteminList)......
  • 《机器学习》—— 随机森林实现二分类问题
    文章目录一、什么是随机森林二、随机森林的主要特点三、随机森林参数四、案例的代码实现一、什么是随机森林随机森林(RandomForest)是一种集成学习方法,属于监督学习算法,主要用于分类和回归任务。它通过在数据集的多个子集上构建多个决策树,并输出这些树预测结果的众数(......
  • 【数据结构-前缀异或和】力扣1177. 构建回文串检测
    给你一个字符串s,请你对s的子串进行检测。每次检测,待检子串都可以表示为queries[i]=[left,right,k]。我们可以重新排列子串s[left],…,s[right],并从中选择最多k项替换成任何小写英文字母。如果在上述检测过程中,子串可以变成回文形式的字符串,那么检测结果为......
  • 【Kaggle】练习赛《有毒蘑菇的二分类预测》(下)
    前言上篇《有毒蘑菇的二分类预测》(上)用ColumnTransformer和Pipeline技术来提升缺失值和建模的方法,本篇将用特征工程的方法,将特征扩展,由原先的21个特征扩展成118个特征,再用深度学习的方法进行建模以达到较好的成绩,同时,在这篇里增加了上篇没有EDA部分,更好的展示数据集......
  • 信息学奥赛初赛天天练-75-NOIP2016普及组-完善程序-二分答案、二分查找、贪心算法、贪
    1完善程序(单选题,每小题3分,共30分)郊游活动有n名同学参加学校组织的郊游活动,已知学校给这n名同学的郊游总经费为A元,与此同时第i位同学自己携带了Mi元。为了方便郊游,活动地点提供B(≥n)辆自行车供人租用,租用第j辆自行车的价格为Cj元,每位同学可以使用自己携带的钱或......
  • 浅谈二分图
    定义二分图,又称二部图,英文名叫Bipartitegraph。二分图是什么?节点由两个集合组成,且两个集合内部没有边的图。换言之,存在一种方案,将节点划分成满足以上性质的两个集合。性质如果两个集合中的点分别染成黑色和白色,可以发现二分图中的每一条边都一定是连接一个黑色点和一个白......