Search Insert Position
EasyPrompt
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.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104numscontains distinct values sorted in ascending order.-104 <= target <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through the array from the beginning to find the target or its insertion point. It's straightforward but less efficient.
Algorithm
- Iterate through the array
numsfrom indexi = 0ton-1. - For each element
nums[i], check if it is greater than or equal to thetarget. - If
nums[i] >= target, return the current indexi. - If the loop completes, it means the
targetshould be inserted at the end. Return the length of the array.
Walkthrough
We can traverse the array nums with a single loop. For each element nums[i], we compare it with the target. If nums[i] is greater than or equal to the target, we've found the correct position. This is because the array is sorted, so any subsequent element will also be greater. If we find such an element, we return its index i. If the loop finishes without finding any element greater than or equal to the target, it implies that the target is larger than all elements in the array. In this case, the correct insertion position is at the very end of the array, so we return the length of the array.
class Solution { public int searchInsert(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] >= target) { return i; } } return nums.length; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Works correctly for all cases.
Cons
Inefficient for large input arrays.
Does not meet the O(log n) time complexity requirement specified in the problem description.
This is the optimal approach that leverages the fact that the input array is sorted. By repeatedly dividing the search interval in half, we can find the target or its insertion position in logarithmic time.
Algorithm
- Initialize pointers
low = 0andhigh = nums.length - 1. - While
low <= high, do the following: a. Calculatemid = low + (high - low) / 2. b. Ifnums[mid]equalstarget, returnmid. c. Ifnums[mid]is less thantarget, move the search to the right half by settinglow = mid + 1. d. Ifnums[mid]is greater thantarget, move the search to the left half by settinghigh = mid - 1. - If the loop terminates, the
targetis not in the array. Thelowpointer indicates the correct insertion position. Returnlow.
Walkthrough
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
We initialize two pointers, low at the start of the array (index 0) and high at the end of the array (index n-1). We then enter a loop that continues as long as low <= high.
Inside the loop:
- We calculate the middle index
mid. - If
nums[mid]is equal to thetarget, we have found the target and returnmid. - If
nums[mid]is less than thetarget, we know the target must be in the right half of the current search space (if it exists), so we updatelowtomid + 1. - If
nums[mid]is greater than thetarget, the target must be in the left half, so we updatehightomid - 1.
If the loop terminates, it means the target was not found in the array. The value of the low pointer at this point is the index where the target would be inserted to maintain the sorted order. This is because the loop invariant maintains that all elements to the left of low are smaller than the target, and all elements to the right of high are larger than the target. When low > high, low points to the first position where an element is greater than or equal to the target.
class Solution { public int searchInsert(int[] nums, int target) { int low = 0; int high = nums.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } // If the loop finishes, target is not found. // 'low' is the insertion point. return low; }}Complexity
Time
O(log n)
Space
O(1)
Trade-offs
Pros
Extremely efficient, with logarithmic time complexity.
Meets the problem's performance requirements.
Optimal solution for sorted arrays.
Cons
Can be slightly tricky to implement correctly, especially handling the edge cases and the final return value when the target is not found.
Solutions
Solution
class Solution {public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = (left + right) >>> 1; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; }}/** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function ( nums , target ) { let left = 0 ; let right = nums . length ; while ( left < right ) { const mid = ( left + right ) >> 1 ; if ( nums [ mid ] >= target ) { right = mid ; } else { left = mid + 1 ; } } return left ; };class Solution {public: int searchInsert(vector<int> &nums, int target) { int left = 0, right = nums.size(); while (left < right) { int mid = left + right >> 1; if (nums[mid] >= target) right = mid; else left = mid + 1; } return left; }};class Solution : def searchInsert ( self , nums : List [ int ], target : int ) -> int : left , right = 0 , len ( nums ) while left < right : mid = ( left + right ) >> 1 if nums [ mid ] >= target : right = mid else : left = mid + 1 return leftVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.