自学内容网 自学内容网

二分查找算法——部分OJ题详解

目录

关于二分查找算法

部分OJ题详解

704.二分查找

一,分析题目

二,细节处理 

三,题目代码 

四,*总结朴素模板 

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

一,查找左端点

二,处理左端点细节 

 三,查找右端点

四,处理右端点细节

五,题目代码

六,总结查找区间左边和区间右边的模板

69.x的平方根

 35.搜索插入位置

 21.山脉数组的峰顶索引

162.寻找峰值

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

 剑指offer 53 - Ⅱ.o~n-1中缺失的数字


关于二分查找算法

  1. 我们曾经在C语言学的二分查找算法,其实是一个“最朴素”或者说“最简单”的一个二分查找算法,学习算法,最好的方式就是通过真正的题目例子来讲解,因为第一次接触一个新算法时,记死概念效率是非常低下的:“实践是检验真理的唯一标准”
  2. 二分查找算法是我们目前阶段学习的算法中:最恶心,细节最多,最容易写出死循环的算法
  3. 但是如果真正掌握了二分查找算法后,就会编程最简单的算法
  4. “二分算法只适用于数组有序的情况”,这句话其实不准确,准确的说法是,只要一个题目满足某种规律,就可以用二分查找算法,不论是否有序
  5. 最后我们就会把二分查找算法总结成几个模板,利用模板能很快速地解决很多题目
  6. ①朴素的二分模板    ②查找左边界的二分模板    ③查找右边界的二分模板。三个模板总代码不超过20行
  7. 第一个模板在第一个题目讲,第二个和第三个模板在第二题讲,第一个模板是朴素的,朴素代表简单而简单代表有局限性,后面两个是万能的模板,但是细节很多

部分OJ题详解

704.二分查找

704. 二分查找 - 力扣(LeetCode)

解释下这道题:给一个有序数组nums,然后给我们一个值target,写一个函数搜索nums中target的值,返回下标,不存在则返回-1,题目很简单,下面我们来分析下这道题:

一,分析题目

  1. 首先是暴力解法:从左往右遍历,找到数就返回下标,没找到就返回-1。虽然这样的效率是O(N),但是并没有用到我们“数组已经有序”这个条件,所以我们来优化一下
  2. 暴力算法的缺点就是“每次判断只能舍弃一个数”,假设要查找数组是[1, 2, 3, 4, 5, 6, 7, 8],target是5,假设我们像拿4和5做比较,4比5小,那么我们就可以舍弃所有比4小的数了,然后再和7比,这样两次比较就可以舍弃大部分数,效率相比暴力解法高很多
  3. 好,来了哈,二分查找的重要特性:当根据某一规律找到一个点,能够通过这个点把一个数组分成两部分,根据规律舍弃一半,然后再另一半继续查找,这样的题目数组就具有“二段性”;当数组无序时,如果依然能根据规律把数组分成两部分,也可以说该数组有二段性,然后根据某个规律能抽象出一个算法,就是“二分查找算法”
  4. 假设一条线代表数组,我可以找中间的点,也可以找1/3和1/4的点,只要能分出两部分的点都可以,但是我们建议选中点,因为这涉及数学概念学的数学期望知识,我们不管,只需要知道用中点的时间复杂度是最小的就可以啦

假设以一条直线为数组,来分析下二分查找算法:mid是中点下标,定义left和right双指针

1,x < t:改变左边界:left = mid+1, 改变中点:mid = (right - mid) / 2; 

2,x > t:改变右边界:right = mid - 1,改变中点:mid = (mind - left) / 2;

3,x = t:返回结果 

二,细节处理 

 有几个细节需要注意一下:

  1. 当left = right,也就是数组缩小到一个数的时候,也要循环判断,所以循环条件是while(left <= right),循环结束条件为:left > right
  2. 为什么上面的算法是正确的? 是从暴力算法优化过来的,前者是对的,那么后者肯定是对的
  3. 该算法时间复杂度为什么比暴力低?当循环一次的时候,会把区间划分成n/2,两次时,就是n/4,三次时就是n/8 --> x次时就是1,所以x就是我们的时间复杂度为O(logN),这绝对是比O(N)快的(在算法中logN的算法并不常见)

三,题目代码 

 题目的二分算法代码如下:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            //盲目用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;
    }
};

四,*总结朴素模板 

//根据二段性,填入具体的条件即可 
while(left <= right) //一定要写成<=,因为当数组只有一个数的时候也是要判断的
        {
            int mid = left + (right - left) / 2;  //防溢出
            if(......) 
            {
                left = mid + 1;
            }
            else if(......)
            {
                right = mid - 1;
            }
            else
            {
                return ......;
            }
        }

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

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

先来解释下题目: 给一个升序数组nums和一个目标值target,找出目标值在数组中的开始位置和结束位置,并且时间复杂度必须为O(logN),如果没有target,或者nums是空数组就返回[-1, -1]

题目看起来很简单,描述也很短,但是这一道题其实非常难,下面我们来分析下这道题,通过这道题的分析我们来把二分算法的最重要的逻辑给搞清楚:

一,查找左端点

  1. 首先是暴力解法:暴力解法,就是遍历一次,当第一次遇到目标数字,用begin标记,然后继续遍历,找到目标数字的最后一个位置时就用end标记,返回begin和end,时间复杂度为O(N)。缺点大致和上个题目一样,这里不再赘述
  2. 然后是前面讲的朴素二分算法,设立左右指针,这样可以解决问题,但是时间复杂度依旧很高,因为假设有5个8,我们用中间值的方法找到了第三个8,但是我们不知道这个8是开头还是结尾,所以还得去前面或后面找,变成“伪二分算法”
  3. 接下来我们对朴素二分“再优化”,假设nums为[1, 2, 3, 3, 3, 4, 5]target为3,可以把数组划分为[1, 2]3以及它右边所有的数这两个区域,左边的值全小于3,右边的值全大于等于3,二段性成立。

 下面是算法步骤,查找左端点的核心步骤是第2和第3步:

1,和朴素算法一样,定义双指针,然后mid在数组中间

2,当mid < t,也就是mid落在了左边区间,左边区间全是小于mid的,更新左边界:left = mid+1

3,当mid >= t,也就是落在右区间[3, 3, 3, 4, 5],一般会更新right = mid - 1,但是这道题不能直接更新,因为假设mid为第一个3,也就是起始位置,那么更新后的right和left就是前面的[1, 2]了,没有结果了,所以right = mid,不要再-1,然后[left, right]继续寻找

二,处理左端点细节 

上面的步骤其实不难,真正的难点其实是下面的细节处理,这个处理主要针对上面的第三步right问题(假设nums还是[1, 2, 3, 3, 3, 4, 5],target = 3):

----------循环条件----------

  1. 循环条件:必须选择left < right而不能选择 <= ,因为right在移动后,会有三种情况①[mid, right]有结果,也就是right在目标连续区域里面,包含开头  ②[mid, right]之间的数全大于t  ③区间的数全小于t
  2. 首先看情况①:我们的目标是先找左端点,[left, mid],假设为[1, 2, 3, 3],包含左端点,这时,left处于不合法区间,right处于合法区间, 以步骤3为前提,right变化时是right = mid,所以right绝对不会超过合法区间,而left是一直往右走尝试跳出不合法区域,所以当left == right也就是left和right相遇时,相遇的值就是我们的最终结果,无需判断。
  3. 然后是情况②:就是[mid, right]全是大于t的,假设[mid, right]为[4, 5],这时候right会一直往左边移动,直到与left相遇,因为全大于t时,会只命中步骤三的条件,right一直等于mid,然后mid重新计算,依次循环,而且步骤三中left是不动的,因此相遇时,没有最终结果,只要判断相遇的值是否等于t,如果等于t就记录下标,为左端点,如果不等于就返回[-1, -1]
  4. 最后是情况③:当全小于t时,只会命中步骤2,也就是left一直往左移动,right不动,当相遇时,依旧判断相遇值是否等于t,和上面第三点的处理是一样的

问题:当right = left时,就是最终结果,无需再次进入循环判断,返回是或不是即可。为什么不再判断呢?

解答:如果判断,就会陷入死循环,因为当left = right时,会命中步骤3,mid会一直计算出同样的位置,right也会一直在相同位置上,就这样一直循环下去,于是造成了死循环 

 ----------求中点操作----------

  1.  两种方法①left + (right - left) / 2  ②left + (right - left + 1) / 2,对于第一题“704.二分查找”的题目来说两种求中点的方法都可以,但是到了这道题就不行了
  2. 假设数组为[1, 2, 3, 4],如果我们用方法①求中点,求出来的是“ 2 ”这个位置,方法②求出来的是“ 3 ”的位置,这两种情况在朴素二分是都可以的,但是在这里就不行了,下面是极端情况
  3. 假设我们最后一次操作求中点的时候,假设数组为[3, 4],left指向3,right指向4,如果选择方法②求中点,求出来的mid指向right的位置,次数命中步骤2,left会移动到mid+1的位置也就是right后一个位置,程序正常退出;如果命中步骤3,那么left和right是都不动的,mid和right依旧处于同一位置,会形成死循环
  4. 所以这道题我们必须用方法①来求中点,mid会落在left的位置,假设命中步骤1,left = mid + 1,此时和right相遇,进入判断逻辑;如果,命中步骤3,right = mid。right == left,程序也是正常退出,不会造成死循环

 三,查找右端点

前置步骤和查找左端点一样,这里不再赘述

假设数组依旧为[1, 2, 3, 3, 3, 4, 5],target = 3。划分的区域为[1, 2, 3, 3, 4]和[4, 5]这两个,可以发现左边区域是小于等于3的,右边区域是大于3的,二段性成立

下面是找右端点的核心步骤:

1,依旧定义双指针left和right,还有中点mid

2,找右端点就是和找左端点反过来,当mid <= t,mid落在左边区间,left往右移动,left = mid,,不能是left = mid + 1,原因和上面的细节处理一样

3,x > t时,mid落在右区间,right往左移动,right = mid - 1(其实就是和左端点反过来)

四,处理右端点细节

 ----------循环条件----------

  1.  和上面一样,循环条件必须是left < right,不能等于,因为会死循环
  2. 并且left和right相遇的位置直接返回是或不是,无需再次进入循环判断

----------求中点操作----------

  1.  两种方法①left + (right - left) / 2  ②left + (right - left + 1) / 2。和上面反过来,求左端点必须是方法①,但是求右端点必须是方法②
  2. 假设数组为[3, 4] ,left指向3,right指向4,假设用方法①,mid落在4的位置,此时命中步骤2,left = mid,很明显有死循环;命中步骤3时,left不动,right = mid - 1,也就是left前面的那一个位置,循环会正常退出
  3. 用方法②时,mid落在4的位置上,如果命中步骤2,left = mid + 1,left与right相遇,返回是或不是,循环正常结束;假设命中步骤3,right = mid - 1,right和left依旧相遇,循环也正常退出,所以求右端点时,求中点应该用方法②,和左端点反过来

五,题目代码

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        if(nums.size() == 0) return {-1, -1}; //处理空数组情况
        //1,先二分查找左端点
        int left =0, right = nums.size() - 1;
        int begin = 0; //记录左端点位置,不设立右端点了,因为如果有左端点,那么必定也有右端点,直接返回left和right相遇的位置即可
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) 
            {
                left = mid + 1;
            }
            else //nums[mid] >= target
            {
                right = mid;
            }
        }
        //判断left和right相遇位置是否有结果
        if(nums[left] != target) 
        {
            return {-1, -1};
        }
        else
        {
            begin = left; //标记左端点位置
        }

        //2,开始二分查找右端点
        left = begin; //优化,left仅需从左端点开始,去掉左边的区间
        right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) 
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return {begin, right};
    }
};

六,总结查找区间左边和区间右边的模板

----------查找左端点模板----------

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;
            }
        }

当下面出现-1的时候,上面就+1 

69.x的平方根

69. x 的平方根 - 力扣(LeetCode)

解释下题目:给一个正整数x,计算返回x的算数平方根,也就是大于0的平方根;如果平方根是无限循环的小数,则只返回整数部分;并且不能使用其它的求平方根的内置函数如pow,下面来分析下这道题:

  1. 首先是暴力算法;直接构建一个递增的数组[1, 2, 3, 4, 5, 6, 7, ......],假设target = 17,直接暴力地去把数组中的每一个值做平方,把每个结果去枚举出来,然后和target做对比,直到找到合适的数。下面我们来优化暴力算法
  2. 其实我们没必要真的去构建这么一个数组,由于一个数target的算数平方根是小于等于target这个数的,所以可以在逻辑上构建一个数组,左端点left为0,然后右端点right直接为target,然后mid也是直接mid = left + (right - left) / 2,当然通过上面的例子,求mid时要不要+1还是要讨论下的
  3. 然后逻辑上数组有序,所以也可以用二分算法,分成两个区域,左边全小于等于target,右边全大于target,然后这个题目是求左区间的右端点,故可以用求右端点的二分算法模板来解题

1,left从1开始,因为1的平方也是1,right从target开始,
2,mid落在左区间,mid*mid <= x:;left = mid,因为mid可能正好等于x
3,mid落在右区间,mid*mid > x:right = mid - 1

class Solution {
public:
    int mySqrt(int x) 
    {
        if(x < 1) return 0; //如果小于1,那么平方根必定小于1,舍去小数就是0
        int left = 1, right = x;
        while(left < right)
        {
            long long mid = left + (right - left + 1) / 2; //用long long,防止后面平方溢出
            if(mid*mid <= x)
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left;
    }
};

 35.搜索插入位置

35. 搜索插入位置 - 力扣(LeetCode)

解释下题目: 给一个的排序好的数组,在数组中找到目标值target,并返回索引,如果目标值不再,返回它“即将会被顺序插入”的位置,数组无重复元素,题目很简单,下面分析下题目:

  1. 暴力算法就不解释了,还是老一套。这道题也很明显能用二分,因为数组依旧可以分为两部分,左边小于target,右边大于等于target
  2. 所以我们只需要找到右区间的左端点,直接用模板即可
  3. 然后就是要插入的位置,该位置应该就是第一个比目标值target大的位置,假设数组为[1, 2, 3, 5],target为4,由于数组中没有4,要插入,那么就是插入在5的位置,返回原数组5的位置即可
  4. 总的来说如果数组中有target,就返回右区间的左端点位置,没有就返回该位置+1的值

1,mid落在左区间,mid < t:left = mid + 1
2,mid落在右区间,mid >= t:right = mid

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

        //假设数组是[1, 2, 3],我要插入4,最终left会停留在3的位置,所以要+1
        if(nums[left] < target) return left + 1; 
        else return left;
    }
};

 21.山脉数组的峰顶索引

852. 山脉数组的峰顶索引 - 力扣(LeetCode)

 题目很简单就不解释啦,下面来分析下这道题:

  1. 首先是暴力解法,定义两个同向指针,一个在前一个在后,依次遍历数组,当前面指针的数比后面小的时候,后面的值就是该山峰数组的最大值
  2. 这道题是经典的数组“无序”的情况下依旧可以用二分算法的题目,因为前面说过只要有二段性,就可以用二分算法
  3. 这道题我们也可以分成两部分,假设数组为nums = [1, 2, 3, 4, 3, 2, 1],一部分就是[1, 2, 3, 4],是升序数组,另一部分是[3, 2, 1],为降序数组,所以可以用二分算法,用在左区间找右端点的模板即可

1,mid落在左边,arr[mid] > arr[mid - 1]:后一个数比前一个数大,所以left = mid
2,mid落在右边,arr[mid] <= arr[mid - 1]:后一个数比前一个数小,所以right = mid - 1

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

162.寻找峰值

162. 寻找峰值 - 力扣(LeetCode)

 解释下题目,这道题其实就是把上一题的“一个山峰”变成了“多个山峰”,返回任意一个山峰的索引即可,下面我们来分析下这道题:

首先要明白一下,题目描述的山峰形状有下面三种:

  1.  暴力解法:从数组下标为0的位置开始,情况①,刚开始一直往上,走到最后一个位置时也没有往下,返回最后一个位置的索引。  情况②刚开始就直接往下走了,并且走到底也没有上升,返回开始时位置即可。  情况③一开始往上走,然后到达某一个位置后就开始往下走了,返回该位置即可
  2. 用暴力解法其实很复杂,所以我们尝试优化暴力解法:其实这道题和上面那一道山峰题很像
  3. 我们选一个位置为i,那么下一个位置就是i+1;  ①如果arr[i] > arr[i+1],那么这段区间就是一个下降的趋势,在时候左边趋势一定有峰值  ②如果arr[i] < arr[i+1],那么是上升趋势,右边一定有最终结果
  4. 所以这道题的接替思路和上一题是一模一样的,因为题目要求是返回任意一个,所以我们随便找一个峰值返回即可,思路和上一题一致
  5. 这就是二分算法相较于普通解法的优势,这道题的解题代码也是直接用在右区间找左端点的模板
class Solution
{
public:
    int findPeakElement(vector<int>& nums) 
    {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

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

153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

题目有点长,我们浓缩一下:题目中的“旋转一次”就是把数组最后一个数搞到最前面来,旋转两次就是,在旋转一次的基础上,再把最后一个数搞到第一个位置上,以此类推;题目就是给你一个升序的不重复的数组,但是经过多次旋转后,再把旋转后的数组给了你让你操作。下面我们来分析下这道题:

  1. 经过旋转后的数组,假设为[3, 4, 5, 1, 2],我们用可以用一个图来表示:
  2. 其中AB区域就是[3, 4, 5],CD区域就是[1, 2]上面的图我们可以找出二段性:①在A~B区域中,nums[i] > nums[n-1]    ②在C~D中,nums[i] <= nums[n-1],好二段性成立,判断条件有了
  3. 我们要找的,就是C点的值,也就是最小值,然后大致逻辑如下:

1,定义双指针,left和right

2,当mid落在A~B区间时,left往右移动,nums[mid] > nums[n-1]:left = mid + 1

3,当mid落在C~D区域时,right往左移动,nums[mid] <= nums[mid-1] right = mid

class Solution 
{
public:
    int findMin(vector<int>& nums) 
    {
        int n = nums.size();
        int left = 0, right = n - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[n-1]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};

问题:我们代码是以D点为参照物的,上面的全比D大,下面的小于等于D;那么我么你可以不可以以A点为参照物呢?

解答:可以,但是有极端情况。如题目所述,[0, 1, 2, 3, 4, 5, 6, 7]这个数组,旋转7次后和原数组是一样的,完全递增,所以这时候再以A为参照物,就要加一些判断条件 

 剑指offer 53 - Ⅱ.o~n-1中缺失的数字

LCR 173. 点名 - 力扣(LeetCode)

 解释下题目:某班级有n个学生,学号依次排序,为0 ~ n-1,升序,假设有一名同学缺席,返回缺席同学的学号。下面来分析下这道题:

  1. 这道题比较简单,解法很多,但是这种一题多解的题,在面试的时候很喜欢问,所以我们来介绍下多种解法
  2. 首先可以用哈希表,把数组的数全扔哈希表里去,然后看哪个位置是0,就返回这个位置
  3. 直接找,用一个for循环遍历,因为数组是严格递增的,所以可以一一遍历
  4. 可以用异或的位运算,我们构建一个完整的严格递增的数组,然后把里面的值和题目给我们的数组一一异或一下,这样相同的数会抵消变成0,异或不为0时,就是我们要的数
  5. 高斯求和公式(数学):等差数列求和公式,先把没有缺少的数组的 首项 + 末项 的和 乘以项数再除以2,得到所有数的和,然后依次减去题目数组的数,最后剩下的结果就是我们要的数
  6. 上面的方法时间复杂度都是O(N),并且都有空间消耗,面试的时候只要想到就可以了

下面我们介绍下更优的解法:

先找二段性:

数组①:[0, 1, 2, 4, 5, 6]
数组②:[0, 1, 2, 3, 4, 5]
我们在数组①的2和4和数组②的2和3画一条线,这样就把数组①分成了两段,左边就是和数组②相同,右边就是每个下标对应的值,数组①都比数组②大一,最后我们就要找的就是右边区域的左端点下标

然后我们开始移动指针: 
①mid落在左边区间:nums[mid] == mid,left=mid+1
②mid落在右边区间:nums[mid] != mid,right = mid

有一个细节情况:假设数组是[0, 1, 2, 3],缺失的值是4,这时候二分划分区域时,不存在右边区间,所以left会一直往后走,走到3的位置,但是3不是我们要的值,所以返回的时候要判断一下:也就是如果left走到最右边和right相遇时,所指的值和对比数组是一样的,那么判断这个数组是一个严格递增数组,缺少的是最后一个位置的下一个数 

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

原文地址:https://blog.csdn.net/aaqq800520/article/details/140321162

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!