[!info] related notes 算法面试题型 MOC 二分查找

搜索插入位置

题目

35. 搜索插入位置 - 力扣（LeetCode）

思路

返回第一个 >= target 的下标，即 lower_bound(target)。若目标比所有元素大，返回 nums.length，表示末尾插入位置，不是有效元素下标。原题元素互异；该实现对非递减且有重复的数组也返回最左边界，对空数组返回 0。

搜索区间为 [l, r)：l 左边都小于 target，r 及右边都大于等于 target，循环结束时 l = r。时间 O(log n)，空间 O(1)。

代码（JavaScript）

function lowerBound(nums, target) {
  let l = 0, r = nums.length; // [l, r)
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
  }
  return l;
}

var searchInsert = function(nums, target) {
  return lowerBound(nums, target);
};