Day 1 - binary search

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

1. It is based on binary search method.
2. The trick is return the index where it is supposed to be inserted.
3. In the first attempt, I was confused what variable to use in order to calculate the supposed index
4. All the cases when target is not found, lower_bound is always bigger than upper_bound. (take a look at while condition again.)
5. I tried to divide if/else case for lower_bound > nums.length or upper_bound < 0
6. But it turns out, that is neither necessary nor efficient.
7. Returning lower_bound index 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

• Easy 1656.Design an ordered stream

• Easy 1826.Faulty Sensor - premium membership only

• Medium 2300. Successful Pairs of Spells and Potions

Comments

[So Sun Park]

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 :)