Search Insert Position

How it works

Most languages provide a built-in binary search or lower bound function. These functions return the index where the target is found or the position where it should be inserted to maintain sorted order. Using these avoids reimplementing binary search.

Steps

1. Call the language's built-in binary search function (e.g., bisect_left in Python, lower_bound in C++, Arrays.binarySearch in Java).
2. If the function returns a negative value (Java), convert it to the insertion point (-index - 1).
3. Return the resulting index.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Off-by-One Errors in Binary Search Boundaries

A frequent mistake is using incorrect loop conditions or boundary updates. Using l < r instead of l <= r (or vice versa) without adjusting the logic accordingly can cause the algorithm to miss elements or enter infinite loops. Similarly, setting r = mid instead of r = mid - 1 in certain variants can lead to incorrect results or infinite loops.

Forgetting to Handle the "Insert at End" Case

When the target is larger than all elements in the array, the insertion position should be n (the length of the array). Beginners often forget to account for this case, either returning -1, causing an index out of bounds error, or returning the last index incorrectly. Always ensure your algorithm correctly returns n when the target exceeds all array elements.

from typing import List

import bisect
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};