LeetCode35 Search Insert Position

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a sorted array 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.

You may assume no duplicates in the array.

样例

1
2
3
4
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

思路

将一个数插入到有序数组(数组中没有重复的元素)中去,输出插入的位置。

二分查找即可。知乎上有一个讨论二分查找有几种写法?它们的区别是什么?,可以围观一下~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
if (nums[r] < target) return nums.size();
return r;
}
};
分享到 评论