LeetCode 35: Search Insert Position (Lower Bound Binary Search)

2026-03-19 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 35Binary SearchArrayLower Bound

Today we solve LeetCode 35 - Search Insert Position.

Source: https://leetcode.com/problems/search-insert-position/

English

Problem Summary

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

Key Insight

This is exactly the lower_bound position: the first index i such that nums[i] >= target. If all numbers are smaller, answer is nums.length.

Brute Force and Limitations

Linear scan finds the position in O(n). It works but misses the binary-search requirement and is slower for large input sizes.

Optimal Algorithm Steps

1) Initialize search range as [0, n).
2) Compute midpoint and compare with target.
3) If nums[mid] >= target, keep left half including mid.
4) Else, move left boundary to mid + 1.
5) When loop ends, left is the insertion index.

Complexity Analysis

Time: O(log n).
Space: O(1).

Common Pitfalls

- Mixing closed interval and half-open interval formulas.
- Returning mid directly when equal, then breaking lower-bound invariant.
- Off-by-one errors when target is smaller than all elements or larger than all elements.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid + 1
        return left

var searchInsert = function(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] >= target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
};

中文

题目概述

给定一个升序且元素互不相同的数组，以及目标值 target。若目标存在返回其下标；否则返回按顺序应插入的位置。

核心思路

本题本质是找 lower_bound：数组中第一个满足 nums[i] >= target 的位置。若不存在，则插入到末尾。

暴力解法与不足

从左到右线性扫描可以做，但时间复杂度为 O(n)，不符合二分题目的预期效率。

最优算法步骤

1）使用左闭右开区间 [0, n)。
2）取中点比较 nums[mid] 与 target。
3）若 nums[mid] >= target，收缩右边界到 mid。
4）否则左边界移动到 mid + 1。
5）循环结束时 left 即答案。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 区间定义混乱导致死循环。
- 命中 target 就提前返回，失去 lower_bound 统一写法。
- 边界测试不足（比所有元素小/大）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid + 1
        return left

var searchInsert = function(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] >= target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
};