算法(3)——二分查找

2024-01-01 12:27:55

一、什么是二分查找

二分查找也称折半查找,是在一组有序(升序/降序)的数据中查找一个元素,它是一种效率较高的查找方法。

二、二分查找的原理

1、查找的目标数据元素必须是有序的。没有顺序的数据,二分法就失去意义。


2、数据元素通常是数值型,可以比较大小。


3、将目标元素和查找范围的中间值做比较(如果目标元素=中间值,查找结束),将目标元素分到较大/或者较小的一组。


4、通过分组,可以将查找范围缩小一半。


5、重复第三步,直到目标元素=新的范围的中间值,查找结束。

三、二分查找模板?

1、朴素二分查找模板

2、一般二分查找模板

四、二分查找经典OJ题

4、1 二分查找

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

1、题目描述

2、算法思路

a. 定义 left right 指针,分别指向数组的左右区间。
b. 找到待查找区间的中间点 mid ,找到之后分三种情况讨论:
????????i. arr[mid] == target 说明正好找到,返回 mid 的值

? ? ? ??ii. arr[mid] > target 说明 [mid, right] 这段区间都是?于 target 的,因此舍去右边区间,在左边 [left, mid -1] 的区间继续查找,即让 right = mid - 1 ,然后重复 2 过程;

????????iii. arr[mid] < target 说明 [left, mid] 这段区间的值都是?于 target 的,因此舍去左边区间,在右边 [mid + 1, right] 区间继续查找,即让 left = mid + 1 ,然后重复 2 过程;
c. left right 错开时,说明整个区间都没有这个数,返回 -1

3、算法代码

class Solution {
public:
    int search(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)
            {
                right=mid-1;
            }
            else if(nums[mid]<target)
            {
                left=mid+1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
};

4、2?在排序数组中查找元素的第?个和最后?个位置

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

1、题目描述:

2、算法思路:

?的还是?分思想,就是根据数据的性质,在某种判断条件下将区间?分为?,然后舍去其中?个
区间,然后再另?个区间内查找;
?便叙述,? x 表?该元素, resLeft 表?左边界, resRight 表?右边界。
寻找左边界:
? 我们注意到以左边界划分的两个区间的特点:
? 左边区间 [left, resLeft - 1] 都是?于 x 的;
? 右边区间(包括左边界) [resLeft, right] 都是?于等于 x 的;
? 因此,关于 mid 的落点,我们可以分为下?两种情况:
? 当我们的 mid 落在 [left, resLeft - 1] 区间的时候,也就是 arr[mid] < target 。说明 [left, mid] 都是可以舍去的,此时更新 left mid + 1 的位置, 继续在 [mid + 1, right] 上寻找左边界;
? mid 落在 [resLeft right] 的区间的时候,也就是 arr[mid] >= target 。 说明 [mid + 1, right] (因为 mid 可能是最终结果,不能舍去)是可以舍去的,此时 更新 right mid 的位置,继续在 [left, mid] 上寻找左边界;
? 由此,就可以通过?分,来快速寻找左边界;
注意:这?找中间元素需要向下取整。
因为后续移动左右指针的时候:
? 左指针: left = mid + 1 ,是会向后移动的,因此区间是会缩?的;
? 右指针: right = mid ,可能会原地踏步(?如:如果向上取整的话,如果剩下 1,2 两个元
素, left == 1 right == 2 mid == 2 。更新区间之后, left right mid 的 值没有改变,就会陷?死循环)。
因此?定要注意,当 right = mid 的时候,要向下取整。
寻找右边界思路:
? ? resRight 表?右边界;
? 我们注意到右边界的特点:
? 左边区间 (包括右边界) [left, resRight] 都是?于等于 x 的;
? 右边区间 [resRight+ 1, right] 都是?于 x 的;
? 因此,关于 mid 的落点,我们可以分为下?两种情况:
? 当我们的 mid 落在 [left, resRight] 区间的时候,说明 [left, mid - 1](mid 不可以舍去,因为有可能是最终结果) 都是可以舍去的,此时更新 left mid 的位置;
? 当 mid 落在 [resRight+ 1, right] 的区间的时候,说明 [mid, right] 内的元素 是可以舍去的,此时更新 right mid - 1 的位置;
? 由此,就可以通过?分,来快速寻找右边界;
注意:这?找中间元素需要向上取整。
因为后续移动左右指针的时候:
? 左指针: left = mid ,可能会原地踏步(?如:如果向下取整的话,如果剩下 1,2 两个元
素, left == 1 right == 2 mid == 1 。更新区间之后, left right mid 的值 没有改变,就会陷?死循环)。
? 右指针: right = mid - 1 ,是会向前移动的,因此区间是会缩?的; 因此?定要注意,当 right = mid 的时候,要向下取整。

3、算法代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        int begin=0;
        if(nums.size()==0) return {-1,-1};
        int left=0,right=nums.size()-1;
        while(right>left)   //找左端点
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<target) left=mid+1;
            else right=mid;
        }
        if(nums[left]!=target) return {-1,-1};
        else begin=left;
        left=0,right=nums.size()-1;
        while(right>left)
        {
            int mid=left+(right-left+1)/2;
            if(nums[mid]<=target) left=mid;
            else right=mid-1;
        }
        return {begin,right};
    }
};

4、3 搜索插入位置

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

1、题目描述

2、算法思路

a. 分析插?位置左右两侧区间上元素的特点:
设插?位置的坐标为 index ,根据插?位置的特点可以知道:
? [left, index - 1] 内的所有元素均是?于 target 的;
? [index, right] 内的所有元素均是?于等于 target 的。
b. left 为本轮查询的左边界, right 为本轮查询的右边界。根据 mid 位置元素的信息,分析下?轮查询的区间:
? nums[mid] >= target 时,说明 mid 落在了 [index, right] 区间上,
mid 左边包括 mid 本?,可能是最终结果,所以我们接下来查找的区间在 [left, mid] 上。因此,更新 right mid 位置,继续查找。
? nums[mid] < target 时,说明 mid 落在了 [left, index - 1] 区间上, mid 右边但不包括 mid 本?,可能是最终结果,所以我们接下来查找的区间在 [mid + 1, right] 上。因此,更新 left mid + 1 的位置,继续查找。
c. 直到我们的查找区间的?度变为 1 ,也就是 left == right 的时候, left 或者
right 所在的位置就是我们要找的结果。

3、算法代码

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

4、4 X的平方根

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

1、题目描述

2、算法思路

依次枚举 [0, x] 之间的所有数 i
(这?没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回
了,往后的情况就不会再判断。反?研究枚举区间,既耽误时间,?可能出错)
? 如果 i * i == x ,直接返回 x
? 如果 i * i > x ,说明之前的?个数是结果,返回 i - 1
由于 i * i 可能超过 int 的最?值,因此使? long long 类型

3、算法代码

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

4、5 山峰数组的峰顶

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

1、题目描述

2、算法思路

峰顶的特点:?两侧的元素都要?。
因此,我们可以遍历数组内的每?个元素,找到某?个元素?两边的元素?即可
3、算法代码
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        for(int i=1;i<arr.size()-1;i++)
        {
            if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
            {
                return i;
            } 
            
        }
        return 0;
    }
};

4、5 寻找峰值? ?

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

1、题目描述

2、算法思路寻找?段性:

任取?个点 i ,与下?个点 i + 1 ,会有如下两种情况:
? arr[i] > arr[i + 1] :此时「左侧区域」?定会存在?峰(因为最左侧是负?穷),那么我们可以去左侧去寻找结果;
? arr[i] < arr[i + 1] :此时「右侧区域」?定会存在?峰(因为最右侧是负?穷),那么我们可以去右侧去寻找结果。
当我们找到「?段性」的时候,就可以尝试?「?分查找」算法来解决问题。
3、算法代码
class Solution {
public:
    int findPeakElement(vector<int>& nums) 
    {
        vector<int> ret;
        int left=0,right=nums.size()-1;
        while(right>left)
        {
            int mid=left+(right-left+1)/2;
            if(nums[mid]>nums[mid-1]) left=mid;
            else right=mid-1;

        }
        return left;
    }
};

4、6?寻找旋转排序数组中的最?值

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

1、题目描述

2、算法思路

题?中的数组规则如下图所示:

其中 C 点就是我们要求的点。
?分的本质:找到?个判断标准,使得查找区间能够?分为?。
通过图像我们可以发现, [A B] 区间内的点都是严格?于 D 点的值的, C 点的值是严格?于 D 点的值的。但是当 [C D] 区间只有?个元素的时候, C 点的值是可能等于 D 点的值的。
因此,初始化左右两个指针 left right :然后根据 mid 的落点,我们可以这样划分下?次查询的区间:
? mid [A B] 区间的时候,也就是 mid 位置的值严格?于 D 点的值,下?次查询区间在 [mid + 1 right] 上;
? mid [C D] 区间的时候,也就是 mid 位置的值严格?于等于 D 点的值,下次查询区间在 [left mid] 上。
当区间?度变成 1 的时候,就是我们要找的结果。
3、算法代码?
class Solution {
public:
    int findMin(vector<int>& nums) 
    {
        int tmp=nums[nums.size()-1];
        int left=0,right=nums.size()-1;
        while(right>left)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]>tmp) left=mid+1;
            else right=mid;
        }
        return nums[left];
    }
};

4、7 0~n-1缺失的数字

LCR 173. 点名 - 力扣(LeetCode)

1、题目描述

2、算法思路

关于这道题中,时间复杂度为 O(N) 的解法有很多种,?且也是?较好想的,这?就不再赘述。
本题只讲解?个最优的?分法,来解决这个问题。
在这个升序的数组中,我们发现:
? 在第?个缺失位置的左边,数组内的元素都是与数组的下标相等的;
? 在第?个缺失位置的右边,数组内的元素与数组下标是不相等的。
因此,我们可以利?这个「?段性」,来使?「?分查找」算法。
3、算法代码
class Solution {
public:
    int takeAttendance(vector<int>& records) 
    {
        int left=0,right=records.size()-1,k=0;
        while(right>left)
        {
            int mid = left+(right-left)/2;
            if(records[mid]!=mid) right=mid;
            else left=mid+1;
        }
        return left==records[left]?left+1:left;
    }

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