My Favorite Problems

Let’s first talk about “Binary Search”. Just to be clear, in data structure, we also have “Binary Search Tree”. In Leetcode problems, a lot of seemingly hard problems can be solved efficiently (time complexity and space complexity wise) by Binary Search. Beccause the time complexity of Binary Search is $\quad O(\log n) $. For instance, if we have an array of length $\quad 2^{31} -1 $, then Binary Search will only traverse 31 times to find the number we want. Imagine how long it will take from a linear scan ! The most difficult part using Binary Search to solve problems is (1) when to use Binary Search and (2) if we can use it, how to transform the original problems into forms that we can easily visualize solutions using Binary Search. While the concept behind Binary Search is simple, writing a bug free algorithm is rather tricky. Let’s take a look at a Leetcode problem.