The Self-Taught Computer Scientist

2 x 2 x 2 = 8
3
log
2
(8) = 3
Base
Figure 3.6: Exponential notation versus logarithmic notation

---

Introduction to Algorithms
32
In this case, 
bisect_left
returned 1 because 
'banana'
is at index 1 in 
sorted_fruits
. If the item 
you are looking for is not in your sorted iterable, 
bisect_left
returns where it would be if it were there.
from bisect import bisect_left
sorted_fruits = ['apple', 'banana', 'orange', 'plum']
bisect_left(sorted_fruits, 'kiwi')
>> 2
As you can see, 
'kiwi'
is not in your sorted iterable, but if it were, it would be at index 2.
Because 
bisect_left
tells you where an item should go if it isn’t there, to check if an item is in an 
iterable, you need to see if the index is within the iterable (
bisect
could return a position outside of 
your iterable) and if the item at the index 
bisect_left
returns is the value you are looking for. Here 
is how to use 
bisect_left
to perform a binary search in Python:
from bisect import bisect_left
def binary_search(an_iterable, target):
index = bisect_left(an_iterable, target)
if index <= len(an_iterable) and an_iterable[index] == target:
return True
return False
If 
bisect_left
returns an index within your iterable and that index contains your target, you return 
True
because the item is in your iterable. Otherwise, it is not, and you return 
False
.
Searching for Characters
You know how to search for characters in a list using Python’s built- in linear and binary search tools. 
But what if you had to write a linear or binary search from scratch to search for characters instead 
of numbers? To understand how to search for characters, you need to understand more about how a 
computer stores them.
A character set is a map between characters and binary numbers. Computer scientists use character 
encoding to implement different character sets. In American Standard Code for Information Interchange 
(ASCII), your computer maps each letter of the alphabet to a seven- bit number. Figure 3.7 shows the 
relationship between binary and the different characters in the English language.
For example, the ASCII value of 
A is 1000001 in binary (you will learn more about binary later in 
the book) and 65 in base 10 (the number system you use every day). The binary digit for 
b is 01100010. 
Uppercase letters, lowercase letters, punctuation symbols, numerals, and various control characters 
that indicate actions, such as page breaks and line feeds, all have ASCII codes. There are ASCII codes 

---