【算法挨揍日记】day10——704. 二分查找、34. 在排序数组中查找元素的第一个和最后一个位置

妖狐艹你老母 2024-02-29 07:21 24阅读 0赞

![03da84e08251415d84701ec7e71a15cc.png][]

## 704. 二分查找 ##

[704. 二分查找][704.]

### 题目描述： ###

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

![55caed741a7c40b68103c6b5da80c967.png][]

### 解题思路： ###

> 本题数组是有序的，具有二段性，因此我们可以使用二分算法来解决这个问题
> 
> 值得注意的是：当left和right不断向中间移动的过程中，left和right可能指向同一个位置，而这个位置需要判断，因此我们的循环条件为left<=right

### 解题代码： ###

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

--------------------

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

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

### 题目描述： ###

给你一个按照非递减顺序排列的整数数组 `nums`，和一个目标值 `target`。请你找出给定目标值在数组中的开始位置和结束位置。

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

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

![6d268faee41846d2a75cbfe769ba7e98.png][]

### 解题思路： ###

> 本题我们利用二分来解决左右端点的问题，首先left和right肯定有的
> 
> 我们通过一个示例来了解本题:\[1,2,3,3,3,4,5\]
> 
> **查找左端点**：我们这里用t来代替target（这样比较好叙述）
> 
> ![cee82face16c43f89a5c0dd5af7f0fb5.png][]
> 
>  *  二分的思路操作：我们可以将上述示例分为两个部分，因为我们现在查找左端点，因此我可以将示例分为【\[1,2\],\[3,3,3,4,5\]】
> 
> ![3c738463c6c744f6aadd816d5b41210d.png][]
> 
> 1.  当x<t时,处于【1,2】这个区间，left=mid+1
> 2.  当x>=t时，处于【3,3,3,4,5】这个区间，right=mid（这里不能等于mid-1，因为如果mid=0，right=-1会越界）
> 
>  *  细节处理：
> 
> **循环条件：**
> 
> 1.  left<right **√**
> 2.  left<=right **×**
> 
> 我们选择那种呢？我们来讨论一下：
> 
> ![1a35acc7b9ba4c2c991a1fb79bedc469.png][]
> 
> 1.  有结果
> 2.  全大于t（t1），right一直向左走，最后right为left结束，如果是left<=right会死循环
> 3.  全小于t（t2），left一直向右走，最后left在right右边结束
> 
> 以此我们只能选择第一种不能选择第二种！
> 
> **求中间的操作：**
> 
> 1.  left+(right-left)/2 **×**
> 2.  left+(right-left+1)/2 **√**
> 
> 我们考虑一下极端情况就可以知道了！当只剩下两个元素的时候：
> 
> ![e360862be4cd4cba86562882ca64460d.png][]
> 
> 第一种没有问题，第二种mid=0+2/2=1，当进行left+1操作的时候会发生越界
> 
> **查找右端点****：**
> 
>  *  二分的思路操作：我们可以将上述示例分为两个部分，因为我们现在查找左端点，因此我可以将示例分为【\[1,2,3,3,3\].\[4,5\]】
> 
> ![1fe409b39a2344caa5c262663ece265e.png][]
> 
> 1.  当x<=t时,处于【1,2,3,3,3】这个区间，left=mid
> 2.  当x>t时，处于【4,5】这个区间，right=mid-1
> 
>  *  细节处理：
> 
> **循环条件：**
> 
> 1.  left<right **√**
> 2.  left<=right **×**
> 
> 还是选择left<right
> 
> **求中间的操作：**
> 
> 1.  left+(right-left)/2 **√**
> 2.  left+(right-left+1)/2 **×**
> 
> 我们考虑一下极端情况就可以知道了！当只剩下两个元素的时候：
> 
> ![e360862be4cd4cba86562882ca64460d.png][]
> 
> 第一种当mid=0+1/2=0时，right=mid-1越界，第二种没有问题

### 解题代码： ###

class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            //特殊情况处理一下
            if(nums.size()==0)return {-1,-1};
            int left=0,right=nums.size()-1;
            vector<int> ret;
            //查找左端点
            while(left<right)
            {
                int mid=left+(right-left)/2;
                if(nums[mid]<target)left=mid+1;
                if(nums[mid]>=target)right=mid;
            }
            //当left==right时就是结果
            if(nums[left]!=target)return {-1,-1};
            else ret.push_back(left);
            //查找右端点
            left=0,right=nums.size()-1;
            while(left<right)
            {
                int mid=left+(right-left+1)/2;
                if(nums[mid]<=target)left=mid;
                if(nums[mid]>target)right=mid-1;
            }
            if(nums[right]!=target)return {-1,-1};
            else ret.push_back(right);
            return ret;
        }
    };

### ![11189b7b339c4ddea36012af9e27116a.gif][] ###

[03da84e08251415d84701ec7e71a15cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/14ccf63478c24aa481a7828d66eae427.png
[704.]: https://leetcode.cn/problems/binary-search/
[55caed741a7c40b68103c6b5da80c967.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/faec71bd2c854074acd86c0f8ba443b9.png
[34.]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
[6d268faee41846d2a75cbfe769ba7e98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/e754ee91348e40e7a45b928340b2a27f.png
[cee82face16c43f89a5c0dd5af7f0fb5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/2655c1aaa3074c0f98efdd60704aa79d.png
[3c738463c6c744f6aadd816d5b41210d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/d9568ccd24414c42b75a9d4909842bef.png
[1a35acc7b9ba4c2c991a1fb79bedc469.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/d2003009f92d44f99bf183a3e2820d19.png
[e360862be4cd4cba86562882ca64460d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/a9866b22fd7547129dd75f0be390e855.png
[1fe409b39a2344caa5c262663ece265e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/173edaaf60d447db9807f1e92d30c99e.png
[11189b7b339c4ddea36012af9e27116a.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/258c6e92c207481197cc28f191636e69.png