The Self-Taught Computer Scientist

Introduction to Algorithms
26
Here is a linear search algorithm in Python:
def linear_search(a_list, n):
for i in a_list:
if i == n:
return True
return False
a_list = [1, 8, 32, 91, 5, 15, 9, 100, 3]
print(linear_search(a_list, 91))
>> True
The first part of your program calls your 
linear_search
function and passes in a list and the number 
to search for, 
n:
a_list = [1, 8, 32, 91, 5, 15, 9, 100, 3]
print(linear_search(a_list, 91))
In this case, 
n is 91, so your algorithm is looking to see if 91 is in 
a_list
.
You then use a 
for
loop to iterate through each element in 
a_list
:
for i in a_list:
Next, you use an 
if
statement to compare each element in 
a_list
to 
n
:
if i == n:
If there is a match, you return 
True
. If you make it through the list and there is no match, you 
return 
False
:
for i in a_list:
if i == n:
return True
return False
When you run your program, it returns 
True
because the number, 
n (in this case, 91), is in 
a_list
:
print(linear_search(a_list, 91))
>> True
If you rerun your program but search for 1,003 instead of 91, your program will return 
False
because 1,003 is not in 
a
_
list
:
print(linear_search(a_list, 1003))
>> False

---

Chapter 3 Search Algorithms
27
When to Use a Linear Search
A linear search’s time complexity is O(
n). In the worst- case scenario, in a list of 10 items, your algorithm 
will take 10 steps. The best- case scenario for a linear search is O(1) because the item you are looking 
for could be the first item in the list, so your algorithm will take only one step because it stops as soon 
as it finds a match. On average, a linear search will take 
n/2 steps.
You should consider using a linear search when your data is not sorted. Sorted data is data arranged 
in a meaningful way. For example, you can sort a list of numbers sequentially (either ascending or 
descending):
# Unsorted List 
the_list = [12, 19, 13, 15, 14, 10, 18]
# List Sorted in Ascending Order 
the_list = [10, 12, 13, 14, 15, 18, 19]
If your data is sorted, you can use a more efficient binary search, which you will learn about shortly.
When you are programming in the real world, instead of writing your own linear search, you can 
use Python’s built- in keyword 
in
. Here is how to perform a linear search on a list of numbers using 
Python’s 
in
keyword:
unsorted_list = [1, 45, 4, 32, 3]
print(45 in unsorted_list)
>> True
Using Python’s 
in
keyword, you performed a linear search on 
unsorted_list
in just one line of code.
In the examples so far, you’ve searched only for numbers. You can also use a linear search to find 
characters in strings. In Python, you can search for a character in a string using a linear search like this:
print('a' in 'apple')
Binary Search
A binary search is another, faster algorithm for searching a list for a number. However, you cannot 
use a binary search on every data set because it works only when your data is sorted.
A binary search searches for an element in a list by dividing it into halves. Suppose you have the list 
of numbers shown in Figure 3.1 sorted (from lowest to highest) and you are looking for the number 19.