Notes on Algos and Datastructures

Binary Search Algorithm

• A binary search algo finds an item in a sorted list in O(log(n)) time
• A brute force approach would walk through the whole list taking O(n) time

Approach

Assuming we have a list of sorted numbers

1. Start with middle number, is it bigger or smaller than our target number?
2. We've effectively divided the problem in half
3. Repeat the same approach of starting in the middle on new half-size problem

Can do this iteratively