# 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(*n*2). 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!).