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

You must write an algorithm with O(log n) runtime complexity.

Examples

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2
Explanation: The target value 5 is found at index 2.

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1
Explanation: The target value 2 is not found, so it would be inserted at index 1.

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4
Explanation: The target value 7 is not found, so it would be inserted at index 4 (after all elements).

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0
Explanation: The target value 0 is not found, so it would be inserted at index 0 (before all elements).

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4

Thinking Process

  1. Lower Bound Pattern: This problem is a direct application of the lower bound binary search pattern
  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search (this problem) O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Solution

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

Solution Explanation

Approach: Standard binary search (this problem)

Key idea: 1. Lower Bound Pattern: This problem is a direct application of the lower bound binary search pattern

How the code works:

  1. Lower Bound Pattern: This problem is a direct application of the lower bound binary search pattern
    • The search space must shrink monotonically each step.
    • Decide which half still satisfies the predicate, discard the other.
    • Use mid = left + (right - left) / 2 to avoid overflow.

Walkthrough — input nums = [1,3,5,6], target = 5, expected output 2:

The target value 5 is found at index 2.

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Lower Bound Pattern: This problem is a direct application of the lower bound binary search pattern
  2. Unified Logic: The same algorithm handles both finding and inserting cases
  3. Exclusive Right Bound: Using right = nums.size() (exclusive) simplifies boundary handling
  4. Loop Invariant: At each step, we maintain that the insertion position is in [left, right]

References

Template Reference