35. Search Insert Position
Model: qwen2.5-coder:14b
Topics: Array,Binary Search
FAANG asked: 1
Acceptance rate: 42.9%
Problem Breakdown
The problem requires finding the position of a target value in a sorted array of distinct integers. If the target is found, return its index; otherwise, return the index where it would be inserted to maintain the sorted order. The input is a sorted array nums and an integer target. The output is an integer representing the insertion index.
Inputs:
- A sorted array of distinct integers (
nums) - An integer (
target)
Outputs:
- An integer representing the index where the target should be inserted
Implicit Constraints or Edge Cases:
- The array can be empty.
- The target could be less than the smallest element, equal to an element in the array, or greater than the largest element.
Intuition
A brute-force approach would involve iterating through the array and checking each element until we find the correct position. This method has a time complexity of O(n), which is inefficient for large arrays.
The key insight is that since the array is sorted, we can use binary search to achieve a more efficient solution with a time complexity of O(log n). Binary search works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half.
Approach
- Initialize Pointers: Start with two pointers,
leftandright, representing the current search bounds. - Binary Search Loop:
- Calculate the middle index
mid. - If the element at
nums[mid]is equal to the target, returnmid. - If the element at
nums[mid]is less than the target, move theleftpointer tomid + 1. - If the element at
nums[mid]is greater than the target, move therightpointer tomid - 1.
- Calculate the middle index
- Insertion Point: When
leftexceedsright, the loop terminates, andleftwill be the correct insertion index.
Complexity Analysis
- Time Complexity: O(log n) because we are using binary search.
- Space Complexity: O(1) as we are only using a constant amount of extra space for pointers.
Solution
def searchInsert(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
Edge Cases Handled
- Empty Array: If the array is empty,
leftwill remain 0, which is the correct insertion index. - Target Less Than Minimum Element: The loop will terminate with
leftat 0, indicating the target should be inserted at the beginning. - Target Greater Than Maximum Element: The loop will terminate with
leftequal to the length of the array, indicating the target should be inserted at the end. - Single Element Array: Handles correctly by adjusting
leftandrightpointers based on comparison.