Chapter 1: Big O notation & Binary Search

• Binary Search

  • Example:

    ```python def binary_search(list,item): low = 0 high = len(list)-1

    while low <= high: mid = (low + high) guess = list[mid] if guess == item: return mid if guess > item: high = mid -1 else: low = mid + 1 return None //The item doesn't exist.

Example: 

list = [1,3,5,7,8,9,11,13]
print binary_search(list,3) =>1
print binary_search(list,8) =>4
```

• Big O Notation

  • establishes a worst-case run time

  • Some common Big O run times

    • O(log n), also known as log time. Example: Binary search.

    • O(n), also known as linear time. Example: Simple search.

    • O(n log n*). Example: A fast sorting algorithm, like quicksort (coming up in chapter 4).

    • O(n2). Example: A slow sorting algorithm, like selection sort (coming up in chapter 2).

    • O(n!). Example: A really slow algorithm, like the traveling salesperson (coming up next!).