## [Leetcode]35. Search Insert Position(C++)

### 题目描述

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

### 例子

#### 例子 1

Input: `nums = [1,3,5,6], target = 5` Output: `2`

#### 例子 2

Input: `nums = [1,3,5,6], target = 2` Output: `1`

#### 例子 3

Input: `nums = [1,3,5,6], target = 7` Output: `4`

### Constraints

• `1 <= nums.length <= 10^4`
• `-10^4 <= nums[i] <= 10^4`
• `nums` contains distinct values sorted in ascending order.
• `-10^4 <= target <= 10^4`

### 解题思路

``````class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (nums.size() == 0 || nums.back() < target) {
return nums.size();
}

size_t left = 0;
size_t right = nums.size() - 1;
while (left < right) {
size_t mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}

return left;
}
};
``````
• 时间复杂度: O(logN)
• 空间复杂度: O(1)

GitHub 代码同步地址： 35.SearchInsertPosition.cpp

Built with Hugo
Theme Stack designed by Jimmy