Given a sorted array and a target, return the index of the target if it exists or return the index in which target should be inserted.
Example
I: [1,3,5,6], 5
O: 2
I: [1,3,5,6], 2
O: 1
Linear Approach
Scan through the array linearly, find the target or a value bigger than the target
public int searchInsert(int[] nums, int target) {
// good practice to check null or empty input
if (nums == null || nums.length == 0) {
return 0;
}
// linear scan
int i;
for (i = 0; i < nums.length; i++) {
if (nums[i] >= target) {
return i;
}
}
return i;
}
This definite works. Can we do better?
Alternative Approach
Construct a binary search tree then search for the lower bound.
from sortedcontainers import SortedList
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
sorted_list = SortedList()
for num in nums:
sorted_list.add(num)
return sorted_list.bisect_left(target)
Binary Search Example
Consider this example, given input [0,2,3,4,6,7,8,11] find target 6 with the search function below.
func search
Pick a midpoint
Check if the midpoint is the target, return it if so
If smaller than the target, we search right section
If bigger than the target, we search left section
Tracing through this example
midpoint = 4, left = [0,2,3], right = [6,7,8,11]
midpoint < target, search right section
midpoint = 7, left = [6], right = [8,11]
midpoint > target, search left section
midpoint = 6, left = [6], right = [6]
return the index of 6
If we visualize this array as a binary search tree diagram,
[0-11]
/ \
left [0-3] [6-11] right
/ \ / \
[0] [3] [6] [8-11]
/ \
[8] [11]
the worst case of going down a path is log(n), where n is the size of the input array. Because the binary tree is balanced and we have 2^height = n, height=log2(n)=O(log(n)).
Recursive Implementation
A recursive implementation is intuitively sounding because we are applying the same search function either on the left or the right section.
public int searchInsert(int[] nums, int target) {
// good practice to check null or empty input
if (nums == null || nums.length == 0) {
return 0;
}
return search(nums, 0, nums.length - 1, target);
}
private int search(int[] nums, int start, int end, int target) {
// we want to stop when start and end are adjacent to each other
if (start + 1 >= end) {
if (target <= nums[start]) {
return start;
} else if (target <= nums[end]) {
return end;
} else {
return end + 1;
}
}
// binary search
int midpoint = (start + end) / 2;
if (nums[midpoint] == target) {
return midpoint;
} else if (nums[midpoint] < target) {
return search(nums, midpoint + 1, end, target);
} else {
return search(nums, start, midpoint - 1, target);
}
}
The stopping condition is doing a bit extra work here. We will see later that this method can be more convenient in other cases. For this question, we have three possible cases
1. target < A[start], return start
2. A[start] < target < A[end], return end
3. A[end] < target < A[end+1], return end + 1
Iterative Implementation
The recursion only keeps track of start index and end index. We can have two variables outside of the while loop to accomplish the same functionality.
public int searchInsert(int[] array, int target) {
if (array == null || array.length == 0) {
return 0;
}
int start = 0, end = array.length - 1;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (array[mid] < target) {
start = mid;
} else {
end = mid;
}
}
// check the right place to insert
if (target <= array[start]) {
return start;
} else if (target <= array[end]) {
return end;
} else {
return end + 1;
}
}
Time & Space Complexity
Recursive - O(logn) time (logn) space
Iterative - O(logn) time O(1) space
The worst case of searching is going down a full path in the tree diagram above. The length of the full path or equivalently the height of the balanced tree is O(logn).
More formally, we can justify the runtime by solving the recurrence T(n) = T(n/2) + 1.
