二分查找习题篇(上)

标签：二分 right target nums int mid 查找习题 left

1.二分查找

题目描述：

给定⼀个 n 个元素==有序的（升序）==整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2

输出: -1

解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。

n 将在 [1, 10000]之间。

nums 的每个元素都将在 [-9999, 9999]之间。

解法一：暴力解法

从前往后枚举每一个元素，将其与目标值进行对比。

时间复杂度最差为O(N)。

解法二：二分查找算法

当数组具有“二段性”时，我们就可以用二分查找算法。

算法思路：

定义 left ， right 指针，分别指向数组的左右区间。

当left<=right时，下列一直循环：

找到待查找区间的中间点 mid ，找到之后分三种情况讨论：

arr[mid] == target：返回 mid 的值；
arr[mid] > target：让 right = mid - 1，在 [left, right] 的区间继续查找 ,重复 2 过程；
arr[mid] < target：让 left = mid + 1, 在 [left, right] 的区间继续查找，重复 2 过程；

当left>right时，说明整个区间都没有这个数，返回 -1 。

细节问题：

1.循环结束的条件

当left>right

2.为什么是正确的？

二分查找是从暴力解法优化而来的

3.时间复杂度

1次——>n/2¹=n/2

2次——>n/2²=n/4

3次——>n/2³=n/8

…次——>…

x次——>n/2^x=1(当left==right，找到要找的元素时)

2^x=n——>x=logN

因此，二分查找的时间复杂度是logN.

代码实现：

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

朴素二分模版：

while(left<=right)//每次查找的元素都是未知的，所以要取等号
{
int mid=left+(right-left)/2; //防止溢出，替换成left+（right-left+1)也可以，只不过是偶数个元素时，mid有2个中间值，左右均可
if(……)

right=mid-1;
else if(……)

left=mid+1;
else

return ……;
}

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

题目描述：

给你一个按照非递减顺序排列(趋势要么递增要么不变)的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums 是一个非递减数组
-10⁹ <= target <= 10⁹

解法一：暴力查找

从前往后枚举每一个元素，将其与目标值进行对比，相同时记为begin，继续向后寻找，直到找到该数的末尾位置记为end。返回begin,end即可。

时间复杂度最差为O(N)。

解法二：二分查找

==当数组具有“二段性”时，我们就可以用二分查找算法。==接下来我们来寻找该数组的“二段性”.

记左边界为Bleft，右边界为Bright.

1.查找区间的左端点

这里，我们把数组的元素分为两部分——小于target的部分[left,Bleft-1] and 大于等于target的部分[Bleft,right]。

当mid在[left,Bleft-1]的区间，要找左区间，我们可以直接舍去[left,mid]，更新left=mid+1;
当mid在[Bleft,right]的区间，要找左区间，我们可以直接舍去[mid+1,right]，更新right=mid(因为mid可能是最终结果)；
之后在[left,right]上继续寻找左边界。

细节处理：

1.循环条件：

left<right；

left=right时，就是最终结果，无需判断；如果判断，就会死循环。

2.求中点的操作：

正确写法：left+(right-left)/2：求的是靠左的位置（向下调整）。

找左端点时求中点要向下取整。

要是向上调整，判断之后，当mid在[Bleft,right]时，要更新right=mid。再进行下一次判断，要是又面对同样的情况，又更新right=mid……又循环往复……

2.查找区间右端点：

这里，我们把数组的元素分为两部分——小于等于target的部分[left,Bright] and 大于target的部分[Bright+1,right]。

当mid在[left,Bright]的区间，要找右区间，我们可以直接舍去[left,mid-1]，更新left=mid(因为mid可能是最终结果);
当mid在[Bright+1,right]的区间，要找右区间，我们可以直接舍去[mid,right]，更新right=mid-1;
之后在[left,right]上继续寻找右边界。

细节处理：

1.循环条件：

left<right

2.求中点的操作：

正确写法：left+(right-left+1)/2：求的是靠右的位置（向上调整）;

找右端点时求中点要向上取整。

要是向下调整，判断之后，当mid落在[left,Bright]时，要更新left=mid。再进行下一次判断，要是又面对同样的情况，又要更新left=mid……又循环往复……

代码实现：

class Solution
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        // 处理边界情况
        if(nums.size() == 0) 
            return {-1, -1};

        int begin = 0;
        // 1. 二分左端点
        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;
        }
        
        // 判断是否有结果
        if(nums[left] != target) 
            return {-1, -1};
        else 
            begin = left; // 标记⼀下左端点
        
        // 2. 二分右端点
        left = 0, 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;
}

总结切记：分类讨论的代码，就题论题即可。

3.搜索插入位置

题目描述：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

算法思路：

本题数组是一个排序数组，具有“二段性”时，我们就可以用二分查找算法。

设插入位置的坐标为x，根据插入位置的特点可以把数组的元素分为两部分——小于target的部分[left , x-1] and 大于等于target的部分[x , right]。

当mid在[left, x-1]的区间，我们可以直接舍去[left, mid]，更新left=mid+1;
当mid在[x, right]的区间，我们可以直接舍去[mid+1,right]，更新right=mid(因为mid可能是最终结果)；
之后在[left,right]上继续查找。

直到我们的查找区间的长度变为 1 ，也就是 left == right 的时候， left 或者right 所在的位置就是我们要找的结果。

代码实现：

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;
        }
        if(nums[left] < target) 
            return right + 1;
        return right;
    }
};

4.x 的平方根

题目描述：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2

解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

解法一：暴力查找

算法思路：

依次枚举 [0, x] 之间的所有数 i ：

如果 i * i == x ，直接返回 x ；
如果 i * i > x ，说明之前的⼀个数是结果，返回 i - 1 。

由于 i * i 可能超过 int 的最大值，因此使用 long long 类型。

代码实现：

class Solution {
public:
    int mySqrt(int x) {
        // 由于两个较⼤的数相乘可能会超过 int 最⼤范围
        // 因此⽤ long long
        long long i = 0;
        for (i = 0; i <= x; i++)
        {
            // 如果两个数相乘正好等于 x，直接返回 i
            if (i * i == x) return i;
            // 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数
            if (i * i > x) return i - 1;
        }
        // 为了处理oj题需要控制所有路径都有返回值
        return -1;
    }
};

解法二：二分查找

本题数组具有“二段性”时，我们就可以用二分查找算法。

算法思路：

这里，我们把数组的元素分为两部分——平方后小于等于x的部分[1,mid] and 平方后大于x的部分[mid-1, x]。

定义 left ， right 指针，分别指向数组的左右区间。

当left<right时，下列一直循环：

找到待查找区间的中间点 mid ，找到之后分三种情况讨论：

mid*mid<=x：更新left=mid
mid*mid>x：更新right=mid-1

代码实现：

class Solution
{
public:
    int mySqrt(int x) 
    {
        if(x < 1) return 0; // 处理边界情况
        int left = 1, right = x;
        while(left < right)
        {
            long long mid = left + (right - left + 1) / 2; // 防溢出
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

最后，本篇文章到此结束，感觉不错的友友们可以一键三连支持一下笔者，有任何问题欢迎在评论区留言哦~

标签：二分,right,target,nums,int,mid,查找,习题,left
From： https://blog.csdn.net/zoelinkailuo/article/details/143610004

二分查找习题篇(上)