# 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 😎