This problem set is under 'Binary Search' of 'Algorithm 1' section of '14 days Study plan of algorithm'.
Question 35. Search Insert Position
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.
Learning points
- It is based on binary search method.
- The trick is return the index where it is supposed to be inserted.
- In the first attempt, I was confused what variable to use in order to calculate the supposed index
- All the cases when
targetis not found,lower_boundis always bigger thanupper_bound. (take a look atwhilecondition again.) - I tried to divide if/else case for
lower_bound > nums.lengthorupper_bound < 0 - But it turns out, that is neither necessary nor efficient.
- Returning
lower_boundindex is enough for all such cases.
Final code
var searchInsert = function(nums, target) {
let lower_bound = 0;
let upper_bound = nums.length - 1;
let mid;
while(lower_bound <= upper_bound) {
mid = Math.floor((lower_bound + upper_bound) / 2);
if(nums[mid] < target) {
lower_bound = mid + 1;
} else if(nums[mid] > target) {
upper_bound = mid - 1;
} else if (nums[mid] == target) {
return mid;
}
}
return lower_bound;
}
Hands-on example
Let us say we have [1, 3, 5, 6]
1. when target = 0
2. when target = 2
3. when target = 7
1. target = 0, nums = [1, 3, 5, 6]
1st while loop:
- lower: 0
- upper: 3
- mid: (0+3)/2 = Math.floor(1.5) = 1
- nums[mid] > target: move upper down to mid - 1
- upper is updated: 0
2nd while loop:
- lower: 0
- upper: 0
- mid: (0 + 0)/2 = Math.floor(0) = 0
- nums[mid] > target: move upper down to mid - 1
- upper is updated: -1
3rd while loop
- Breaks because it's no longer lower <= upper
Outside while, we have...
- lower: 0
- upper: -1
- mid: 0
- Our target(0) should be located at index 0.
In this case, it seems like
we can use either lower or mid index
2. target = 2, nums = [1, 3, 5, 6]
1st while loop:
- lower: 0
- upper: 3
- mid: (0+3)/2 = Math.floor(1.5) = 1
- nums[mid] > target: move upper down to mid - 1
- upper is updated: 0
2nd while loop:
- lower: 0
- upper: 0
- mid: (0 + 0)/2 = Math.floor(0) = 0
- nums[mid] < target: move lower up to mid + 1
- lower is updated: 1
3rd while loop
- Breaks because it's no longer lower <= upper
Outside while, we have...
- lower: 1
- upper: 0
- mid: 0
- Our target(2) should be located at index 1.
In this case, it seems like
we can only use lower index as a return value.
Now, next case will help us to decide which variable we should use as our answer.
3. target = 7, nums = [1, 3, 5, 6]
1st while loop:
- lower: 0
- upper: 3
- mid: (0+3)/2 = Math.floor(1.5) = 1
- nums[mid] < target: move lower up to mid + 1
- lower is updated: 2
2nd while loop:
- lower: 2
- upper: 3
- mid: (2+3)/2 = Math.floor(2.5) = 2
- nums[mid] < target: move lower up to mid + 1
- lower is updated: 3
3rd while loop
- lower: 3
- upper: 3
- mid: (3+3)/2 = 3
- nums[mid] < target: move lower up to mid + 1
- lower is updated: 4
4th while loop
- Breaks because it's no longer lower <= upper
Outside while, we have...
- lower: 4
- upper: 3
- mid: 3
- Our target(7) should be located at index 4.
In this case, it seems like
we can only use lower index as a return value.
Thus, we can safely assume, what we need to care is lower_bound index at the end.
Similar problem sets to these are
Top comments (1)
Ah thank you! great points, appreciate your feedback.
Haven't used shift operators in js for awhile and it was good to go back and read it again :)