Search Insert Position | Leetcode 35 | Explained in Python

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.

Here’s the [Problem Link] to begin with.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Brute Force Solution (Linear Scan)

Intuition & Approach

Walk the array from left to right.

• At the first element that is ≥ target, return its index.
• If you finish the loop, target belongs at the end, so return len(nums).

Code Implementation

class Solution:
    def searchInsert(self, nums, target):
        # Scan each element once
        for i in range(len(nums)):
            if nums[i] >= target:      # found position or exact match
                return i
        return len(nums)               # insert after the last element

Code Explanation

• The loop examines every element until a suitable slot appears.
• Worst-case touches all n elements.

Time & Space Complexity

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

Conclusion

Straightforward but not efficient for large arrays.

Optimal Solution (Binary Search – Lower Bound)

Intuition & Approach

Binary search for the first index where nums[index] ≥ target.

• Keep variables low and high bounding the current search range.
• Track ans, the best insertion index seen so far, starting at n (meaning “end of array”).
• On each iteration:
  • Compute mid.
  • If nums[mid] ≥ target, record mid in ans and move high left to see if an earlier position qualifies.
  • Otherwise (nums[mid] < target) move low right.

Code Implementation

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        low, high = 0, n - 1
        ans = n                     # default insert position = end

        while low <= high:
            mid = (low + high) // 2  # midpoint of the window

            if nums[mid] >= target:
                ans = mid            # nums[mid] is a valid (or exact) position
                high = mid - 1       # keep searching left half
            else:                    # nums[mid] < target
                low = mid + 1        # search right half

        return ans                   # final insertion index

Code Explanation

• ans always stores the smallest index found so far where nums[index] ≥ target.
• Once low surpasses high, no better position exists, so return ans.

Time & Space Complexity

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

Conclusion

The binary-search method halves the search space each iteration, achieving logarithmic performance with only a few variables, ideal for production use and coding interviews alike.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.