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.

Christian Song

Posts by Collection

portfolio

Portfolio item number 1

Portfolio item number 2

publications

Paper Title Number 1

Paper Title Number 2

Paper Title Number 3

talks

Talk 1 on Relevant Topic in Your Field

Tutorial 1 on Relevant Topic in Your Field

Talk 2 on Relevant Topic in Your Field

Conference Proceeding talk 3 on Relevant Topic in Your Field

teaching

Binary Search

Graph

Random Problems

Tricky Problems

System Design

Sorting