Search Insert Position

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Find the target element index in a sorted array or return the index of where it should be inserted

What is Being Asked?

(One sentence on the actual task.)

• Use Binary Search and find the index

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Solve it in $O(logn)$
• Given a sorted array

Why This Works

(Explain the core reason the solution is correct.)

• Binary Search solves it in $O(logn)$
• Returning l gives the correct answer always
• Example 1
  • Target: 3
  • Array [2]
  • After binary search l would be 1
• Example 2
  • Target: 1
  • Array [2]
  • After binary search l would be 0

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Binary Search
• Two Pointers

Time & Space Complexity

• Time: $O(logn)$ → Reason: Search space is divided in half on each iteration
• Space: $O(1)$ → Reason: No additional memory used

Code

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m - 1
            else:
                l = m + 1
        # return m if nums[m] == target else m if nums[m] > target else m + 1
        return l

Common Mistakes / Things I Got Stuck On

• Which while condition to use l <= r or l < r
• Complicated return statement