每日一题(LeetCode)----二分查找（一）-Toy模板网

这篇具有很好参考价值的文章主要介绍了每日一题(LeetCode)----二分查找（一）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

每日一题(LeetCode)----数组–搜索插入位置

1.题目（35. 搜索插入位置）

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

请必须使用时间复杂度为 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

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的升序排列数组
-104 <= target <= 104

2.解题思路

因为数组是有序的排列数组，且无重复元素，所以可以使用二分来找下标

这里一共有四种情况

（1）数组中找到了目标元素，返回当前目标元素的下标结束

（2）目标元素不存在，应在数组的所有元素之前

（3）目标元素不存在，应在所有的元素之后

（4）目标元素不存在，应在数组中的某个位置

具体实现步骤

1.先找到这个数组的左边界，再找到这个数组的右边界，此时的范围就是整个数组

2.然后进行二分查找

（1）先找到中间位置的那个数，然后与目标值进行比较，

1> 如果当前的数比目标值小的话那么左边界变为中间位置向右一个的位置，继续进行查找

2> 如果当前的数比目标值小的话那么右边界变为中间位置向左一个的位置，继续进行查找

3> 如果当前的数和目标值相等的话，那么找到了

（2）当左边界比右边界大的时候，结束查找

3.那要添加元素的位置就是右边界+1的位置文章来源地址https://www.toymoban.com/news/detail-718549.html

3.代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            //int mid=(left+right)>>1;这里通过学习发现可以进行优化
            //优化如下
            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 right+1;
    }
};

到了这里，关于每日一题(LeetCode)----二分查找（一）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！