Grokking Algorithms

return None
my_list = [1, 3, 5, 7, 9] 
print binary_search(my_list, 3) # => 1
print binary_search(my_list, -1) # => None
EXERCISES
1.1
Suppose you have a sorted list of 128 names, and you’re searching 
through it using binary search. What’s the maximum number of 
steps it would take?
1.2
Suppose you double the size of the list. What’s the maximum 
number of steps now?
Binary search
low and high keep track of which
part of the list you’ll search in.
While you haven’t narrowed it down
to one element …
… check the middle element.
Found the item.
The guess was too high.
The guess was too low.
The item doesn’t exist.
Let’s test it!
Remember, lists start at 0.
The second slot has index 1.
“None” means nil in Python. It 
indicates that the item wasn’t found.

---

Chapter 1
 
 
I
 
 
Introduction to algorithms
10
Running time
Any time I talk about an algorithm, I’ll discuss its running time. 
Generally you want to choose the most efficient algorithm—
whether you’re trying to optimize for time or space.
Back to binary search. How much time do you save by using 
it? Well, the first approach was to check each number, one by 
one. If this is a list of 100 numbers, it takes up to 100 guesses. 
If it’s a list of 4 billion numbers, it takes up to 4 billion guesses. So the 
maximum number of guesses is the same as the size of the list. This is 
called 
linear time
.
Binary search is different. If the list is 100 items long, it takes at most 
7 guesses. If the list is 4 billion items, it takes at most 32 guesses. 
Powerful, eh? Binary search runs in 
logarithmic time
(or 
log time
, as 
the natives call it). Here’s a table summarizing our findings today.
Big O notation
Big O
notation is special notation that tells you how fast an algorithm is. 
Who cares? Well, it turns out that you’ll use other people’s algorithms 
often—and when you do, it’s nice to understand how fast or slow they 
are. In this section, I’ll explain what Big O notation is and give you a list 
of the most common running times for algorithms using it.