Leetcode Challenge #1
Tags: javascript, algorithms, beginners
Published: 2022-07-15 11:09:58

P.S. If you are new here, check my [Challenge Introduction](https://dev.to/miccwan/my-leetcode-practice-diary-3415) before this post!

---

So let's start the challenge.

## The Algorithm Study Plan

I found this [study plan](https://leetcode.com/study-plan/algorithm) in the leetcode home page, it might be a good start for me. For the first part, the plan includes 2~3 problems(most are easy, some medium and no hard) every day. I'll try to finish them each day and maybe 0~2 additional problems to make sure I used the whole hour.

## Today's problems

Today's topic: `Binary Search`


| ID | Name | Difficulty | Problem | Solution |
| --- | --- | --- | --- | --- |
| 704 | Binary Search | easy | [link](https://leetcode.com/problems/binary-search/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0704_binary_search.js) |
| 278| First Bad Version | easy | [link](https://leetcode.com/problems/first-bad-version/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0278_first_bad_version.js) |
| 35 | Search Insert Position | easy | [link](https://leetcode.com/problems/search-insert-position/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0035_search_insert_position.js) |

I've seen many implementations of binary search. They should all be done in _O(log(n))_ time and _O(1)_ space.

The one I love the most is to maintain the `left` and `right` pointers under certain conditions, since it is intuitive to use. This works for all three problems above.

Another interesting implemention I've seen is to maintain one pointer which will be added either `2^k` or `0` in each iteration. 
E.g. 
```js
function binarySearch(arr, target) {
  let index = 0;
  let step = 1 << 20;
  while (step) {
    const next = index + step;
    if (next < arr.length && arr[next] <= target) {
      index = next;
    }
    step /= 2;
  }
  return index;
}
```
One could make use of the constrain of the problem to get the initial step size. Or dynamically find it with another loop.

## Additional Problem

I picked another medium binary search problem today.

| ID | Name | Difficulty | Problem | Solution |
| --- | --- | --- | --- | --- |
| 33 | Search in Rotated Sorted Array | medium | [link](https://leetcode.com/problems/search-in-rotated-sorted-array/) | [link](https://github.com/MiccWan/leetcode/blob/main/js/src/0033_search_in_rotated_sorted_array.js) |

First I come up with the most basic idea: use binary search to find the pivot, then apply binary search on either the first or the second part depends on whether `nums[0] < target`. This takes 53 lines and it's not easy to read.

Then I realize I could simply apply binary search on the whole array since `realIndex = (originalIndex + pivot) % arr.length`.
With this trick, the resulting code is reduced to 40 lines and it's more readable for me! The complexity are still _O(log(n))_ time and _O(1)_ space.

## Conclusion

That's my first post of my practice. Any suggestions would be appreciated! Thanks for your reading.

---

[Home](https://dev.to/miccwan/my-leetcode-practice-diary-3415) | [Next](https://dev.to/miccwan/leetcode-practice-2-51pg) -->