Algorithms Part 1

Binary search

Binary Search has a time complexity of O(log N) which basically means it halves the problem space with each search.

So Given 20 numbers 0 to 20 and the target number is 6. Then

left pointer = 0, Right pointer = 20, MidPoint = (left + right) / 2 = 10

Does MidPoint equal 10? NO! hmm okay is the mid point bigger or smaller than the target value? Since 6 is less the MidPoint we move the right pointer to mid’s value -1 (We know it’s not the current mid-value so we can -1) so now the left pointer is still 0 and the right pointer is now 9. We have just halved the problem space 10 to 20 is no longer being considered. The full process would be:

RP: 20, MP:10, LP:0

RP:9, MP:4, LP:0

RP:9, MP:7, LP:5

RP: 6, MP: 5, LP: 5

RP:6, MP:6 LP:6 <- Found

Ok great and how does this help me?

Well given a sorted an array of 1 * 10⁹ values find the value 5635985?

If we just iterate through the array and search index one by one then on my pretty fast i7 it will take around ~7 seconds, with 5635985 searches. Therefore it has a time complexity of O(N) linear time.

Now let's look at a binary search implementation.

This implementation took 0.001 seconds and only required 26 searches! So that’s 7000 times faster and 5,635,959 fewer searches.

Guessing Game

Below is a very small and simple game were given a limit, you can use a BST to solve the children's game “guess the number” in the most optimal way. If the answer is 8569 then it would only require 12 guesses not bad right 😎