Binary Search

The most obvious use-case of binary search is finding a number in a sorted array.

However, most interview questions involving binary search are not such an obvious application of the algorithm. Rarely would an interviewer ask you to just implement the binary search algorithm.

If an interview question involves searching for a key in a search-space that can be repeatedly halved, chances are your solution is based on (perhaps slightly modified) binary search. For example, in an array of 1’s followed by 0’s, you can determine in constant time whether the last one (the 1 that occurs just before the 0’s begin) is to your right or left (because if you have a 1 to your right, the last one is further down to your right and vice versa).

Common bugs

Can you spot the bug in the code below?

Basic questions

Consider a sorted array with duplicates. How would you determine the first occurrence of a given key? 
For example, in the array 1 2 2 3 4 5 the first occurrence of 2 is at index 1.

Find the integral square root of a given number?

Advanced questions

Find if a given key exists in a rotated sorted array. 
A rotated sorted array is a sorted array in which the last element of the array (rotated 0 or more times) is moved to the beginning of the array. 
60 10 20 30 40 and 40 60 10 20 30 are both rotated arrays of the sorted array 10 20 30 40 60.

Optional reading