Binary Search

We want to search a million records in a database. How will you do it ?

Well, Brute Force ?
Fun Bob: Think Again.

Okay. So let's take a list which is, well, less than a million:

[ 1 2 3 4 5 6 7 8 9 10 ]

Then go through each element and compare it with the search element.

What's the time complexity ?
Why the long faces, it's only O(N).

Let's run it on my million records database. 
 *Gulp*.


We know that the array is sorted. We can leverage that information and try to come up with a solution.

If we divide the array into blocks and search the blocks instead of elements we can save a lot of lookups. Now what's a block you say.

We can divide the array into ranges, [1,5], [6, 10]. These ranges represents blocks.

Block 1: 1 to 5
Block 2: 6 to 10

The element can belong to one of these two blocks. If the search element is 3 we know it won't be in Block 2. We again divide Block 1 into two blocks.

Block 3: 1 to 2
Block 4: 3 to 5

Again 3 cannot be in Block 3. We do this until we find the element 3.

As we're removing half of the elements each time. The time complexity will be O(logN).

Time Complexity:  O(log(N))
Space Complexity: O(log(N)) with Recursion
                                O(1) without Recursion