Problem
Given a sorted array of distinct integers nums and an integer target, return the index if the target is found. Otherwise, return the index where it would be inserted to maintain the sorted order.The algorithm should run in O(log n) time.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,3,5,6]
target = 5 Output
2 Solution
This solution uses Binary Search. Since the array is already sorted, the middle element is compared with the target to determine which half of the array can be ignored.If the middle element is equal to the target, its index is returned immediately. If the target is greater, the search continues in the right half; otherwise, it continues in the left half.
If the target is not found, the left pointer represents the correct position where the target should be inserted.
When the search ends,
left points to the first position where the target can be inserted without breaking the sorted order.
Values before
left are smaller than the target, and values from left onward are greater than the target. Therefore, returning left gives the correct insertion position.
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
Complexity
Each iteration eliminates half of the remaining search space, resulting in a time complexity ofO(log n).
The algorithm uses only a few variables, so the extra space complexity is
O(1).