LeetCode — Easy — Search Insert Position (#35)

Problem Description

https://leetcode.com/problems/search-insert-position/description/

Intuition

Since we’re working with a sorted array and need O(log n) complexity, binary search is the natural choice. The key insight is that even if we don’t find the target, the binary search’s final state (specifically the ‘left’ pointer) will tell us where the element should be inserted.

Approach

1. Use binary search with two pointers (left and right) to search for the target
2. For each iteration:

• Calculate the middle point
• If the middle element is the target, return its index
• If target is greater, search right half by moving left pointer
• If target is smaller, search left half by moving right pointer

3. If target isn’t found, return the left pointer position

• This works because when binary search ends, ‘left’ points to where target should be inserted
• If target is smaller than all elements, left = 0
• If target is larger than all elements, left = array length
• If target belongs between elements, left points to first larger element

Complexity

• Time complexity:
  O(logn) — Binary search divides the search space in half with each iteration
• Space complexity:
  O(1) — Only using a constant amount of extra space for pointers and variables

Code

Java

class Solution {
    public int searchInsert(int[] nums, int target) {
         // Initialize pointers for binary search
        int left = 0;
        int right = nums.length - 1;
        
        // Keep searching while the pointers don't cross
        while (left <= right) {
            // Calculate middle point
            // Using left + (right - left) / 2 instead of (left + right) / 2
            // to prevent potential integer overflow
            int mid = left + (right - left) / 2;
            
            // If target is found, return its index
            if (nums[mid] == target) {
                return mid;
            }
            
            // If target is greater, search in right half
            if (nums[mid] < target) {
                left = mid + 1;
            }
            // If target is smaller, search in left half
            else {
                right = mid - 1;
            }
        }
        
        // If we reach here, target was not found
        // 'left' will be at the position where target should be inserted
        return left;
    }
}