35. 搜索插入位置
题目描述
输入一个元素互不相同的升序数组 nums 和整数 target。
若 target 在数组中，返回它的下标；若不在，返回把它插进数组后仍保持升序时它应处的下标。下标从 0 开始。
要求时间复杂度为 O(log n)。
示例 1
输入：nums = [1,3,5,6], target = 5 输出：2
解释：5 在下标 2。
示例 2
输入：nums = [1,3,5,6], target = 2 输出：1
解释：2 不在数组中，应插在 1 和 3 之间，即下标 1。
示例 3
输入：nums = [1,3,5,6], target = 7 输出：4
解释：7 比所有元素都大，应放在末尾，即下标 4。
数据范围
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums升序且没有重复元素。-10^4 <= target <= 10^4
解题思路
使用 lower_bound 二分。
为什么正确
循环结束 lo=hi 是第一个不小于 target 的位置。
复杂度分析
时间 O(log n)，额外空间 O(1)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def searchInsert(self,a,t):
l,h=0,len(a)
while l<h:
m=(l+h)//2
if a[m]<t:l=m+1
else:h=m
return lclass Solution {
public int searchInsert(int[] a, int t) {
int l = 0, h = a.length;
while (l < h) {
int m = (l + h) / 2;
if (a[m] < t) l = m + 1;
else h = m;
}
return l;
}
}class Solution {
public:
int searchInsert(vector<int>& a, int t) {
int l = 0, h = a.size();
while (l < h) {
int m = (l + h) / 2;
if (a[m] < t) l = m + 1;
else h = m;
}
return l;
}
};func searchInsert(a []int, t int) int {
l, h := 0, len(a)
for l < h {
m := (l + h) / 2
if a[m] < t {
l = m + 1
} else {
h = m
}
}
return l
}var searchInsert = function(a, t) {
let l = 0, h = a.length;
while (l < h) {
const m = (l + h) >> 1;
if (a[m] < t) l = m + 1;
else h = m;
}
return l;
};function searchInsert(a: number[], t: number): number {
let l = 0, h = a.length;
while (l < h) {
const m = (l + h) >> 1;
if (a[m] < t) l = m + 1;
else h = m;
}
return l;
};