What is the binary search pattern in Search Insert Position?

The binary search pattern is used to efficiently find the target index or the correct insertion position in a sorted array. By dividing the search space in half each time, the solution achieves O(log n) time complexity.

How do I handle edge cases in this problem?

Edge cases include scenarios where the target is smaller than the first element, larger than the last element, or where the array is empty. Binary search helps handle these efficiently by adjusting the boundaries appropriately.

What if the target is not found in the array?

If the target is not found, binary search will return the index where the target should be inserted, ensuring the array remains sorted.

How do I implement the binary search for this problem?

Start with two pointers, low and high. While low is less than or equal to high, find the middle index, compare the middle element with the target, and adjust the pointers accordingly until the correct position is found.

What is the time complexity of this problem?

The time complexity is O(log n) because binary search splits the search space in half with each iteration. This ensures that even large arrays can be processed efficiently.

#35

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2: 输入: nums = […

数组二分查找

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums 为 无重复元素 的升序排列数组
-10⁴ <= target <= 10⁴

lightbulb

解题思路

方法一：二分查找

由于 $nums$ 数组已经有序，因此我们可以使用二分查找的方法找到目标值 $target$ 的插入位置。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        return l

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to apply binary search to solve problems efficiently.
question_mark
Experience in handling edge cases like insertion boundaries and array size limits.
question_mark
Understanding of O(log n) time complexity and its application in real-world algorithms.

warning

常见陷阱

外企场景

error
Forgetting to update the boundaries correctly in binary search, leading to incorrect results.
error
Not considering edge cases, like inserting at the start or end of the array.
error
Incorrectly handling arrays with only one element or very large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modifying the problem to handle arrays with duplicate values.
arrow_right_alt
Allowing multiple target values and returning all possible insert positions.
arrow_right_alt
Introducing a constraint where the array is not sorted, requiring sorting before binary search.

help

常见问题

外企场景

继续练习

#34 在排序数组中查找元素的第一个和最后一个位置 #33 搜索旋转排序数组 #4 寻找两个正序数组的中位数