#35

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Search Insert Position

Find the correct index for a target value in a sorted array using binary search, or return the position where it should be inserted.

array binary search

Problem Statement

You are given a sorted array of distinct integers and a target value. Your task is to return the index if the target exists in the array. If the target does not exist, you should return the index where it would be if it were inserted in the correct order.

You need to implement an algorithm with O(log n) runtime complexity to solve this problem. This can be achieved by applying binary search over the valid answer space, ensuring the solution is efficient even for large arrays.

Examples

Example 1

Input: nums = [1,3,5,6], target = 5

Output: 2

Example details omitted.

Example 2

Input: nums = [1,3,5,6], target = 2

Output: 1

Example details omitted.

Example 3

Input: nums = [1,3,5,6], target = 7

Output: 4

Example details omitted.

Constraints

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

Solution Approach

Binary Search Implementation

The key to solving this problem is binary search. We will search for the target in the sorted array. If the target is found, return its index. If not, binary search will help find the correct position for the target by narrowing the search space.

Handling Insertions

When the target is not found in the array, the position where it should be inserted must be determined. Binary search will help us find the left boundary where the target should be inserted to maintain the array's sorted order.

Edge Case Consideration

Consider edge cases like an empty array or the target being smaller than the first element or larger than the last element. Ensure your binary search handles these cases by correctly setting boundaries for insertion.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(log n) because binary search divides the search space in half with each iteration, making it highly efficient. The space complexity is O(1) as the algorithm uses constant extra space.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Binary Search

Since the array $nums$ is already sorted, we can use the binary search method to find the insertion position of the target value $target$.

1

2

3

4

5

6

7

8

9

10

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

Solution 2: Binary Search (Built-in Function)

We can also directly use the built-in function for binary search.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#34 find first and last position of element in sorted array #33 search in rotated sorted array #4 median of two sorted arrays