二分查找插入点

插入点问题要解决什么？

• 给定有序数组与 target, 返回插入后仍保持有序的位置;
• 无重复元素时: 存在 target 返回其下标, 不存在则返回首个大于 target 的位置;
• 有重复元素时: 返回最左边 target 的下标, 不存在同样返回首个大于 target 的位置;

无重复元素时如何实现？

• 区间取闭区间 [start, end], end 初值取数组长度;
• 命中 target 立即返回;
• 循环结束返回 start, 此时 start 指向首个大于 target 的元素;

function binarySearchInsertion(numArray: number[], target: number): number {
  let start = 0;
  let end = numArray.length;
  while (start <= end) {
    const currentIndex = Math.floor((start + end) / 2);
    const value = numArray[currentIndex];
    if (value > target) end = currentIndex - 1;
    else if (value === target) return currentIndex;
    else start = currentIndex + 1;
  }
  return start;
}

有重复元素时如何实现？

• 把 value <= target 与 value === target 合并到同一分支: 命中后继续向左收窄;
• 区间取 [start, end], end 初值取 nums.length - 1;
• 循环结束时 start 落在最左边 target 的位置 (不存在时落在首个大于 target 的位置);

function binarySearchInsertionLeft(numArray: number[], target: number): number {
  let start = 0;
  let end = numArray.length - 1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (target <= numArray[mid]) end = mid - 1;
    else start = mid + 1;
  }
  return start;
}

• 两个版本的时间复杂度均为 O(log n), 空间复杂度 O(1);