Day 1 - binary search
Tags: leetcode, algorithms
Published: 2023-04-08 12:28:09

![Algorithm 1's Binary Search in 14 days study plan of algorithms](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f7sn0o7mhhj6si9rsztl.png)

This problem set is under 'Binary Search' of 'Algorithm 1' section of '14 days Study plan of algorithm'.

## [Question 35. Search Insert Position](https://leetcode.com/problems/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.


![Prompt: Search Insert Position](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ujpoc036t04glkyfc6ma.png)

## Learning points

1. It is based on binary search method.
2. 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 `target` is not found, `lower_bound` is always bigger than `upper_bound`. (take a look at `while` condition again.)
- I tried to divide if/else case for `lower_bound > nums.length` or `upper_bound < 0`
- But it turns out, that is neither necessary nor efficient.
- Returning `lower_bound` index is enough for all such cases.

### Final code 
```js
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

```js
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](https://leetcode.com/problems/design-an-ordered-stream/)

- [Easy 1826.Faulty Sensor - premium membership only](https://leetcode.com/problems/faulty-sensor/)
- [Medium 2300. Successful Pairs of Spells and Potions](https://leetcode.com/problems/successful-pairs-of-spells-and-potions/)

![Relevant or similar problem sets to this quiz](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/07nhcgw6svc6n6oogypo.png)