35. 搜索插入位置

Problem: 35. 搜索插入位置

[TOC]

思路

题目中提到使用$log(n)$的时间复杂度,我们采用二分法,总共存在四种情况,存在target找到了,target在最终区间的左边,target在最终区间的右边,如果找不到该元素,left必定与right,mid相等

复杂度

• 时间复杂度:

$O(log(n))$

• 空间复杂度:

$O(1)$

Code

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