Leetcode Challenge #1

P.S. If you are new here, check my Challenge Introduction before this post!

---

So let's start the challenge.

The Algorithm Study Plan

I found this study plan 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	link
278	First Bad Version	easy	link	link
35	Search Insert Position	easy	link	link

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.

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	link

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 | Next -->