35. 搜索插入位置

LeetCode题目:二分查找

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

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

初始代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        
    }
};

解题思路

二分查找(时间复杂度:O(logn))

看到O(logn)就在想应该用二分查找写了。不过这题需要考虑没找到的情况。

vector下标从0开始。所以right=nums.size()还需要-1。

left和right不相等是为了处理边界。比如vector中只有一个元素时,如果此时没找到,那么left可能等于1,或right可能等于-1.如果此时再去和nums[left]就会数组越界。

那就把这种情况拆出来用if语句表示即可。完整代码如下

完整代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=(left+right)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]>target)
                right=mid-1;
            else if(nums[mid]<target)
                left=mid+1;
        }
        if(target>nums[left])
            return left+1;
        else
            return left;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x