# Searching¶

In [2]:
def search(x, nums):
"""Finds a number in a list

Paramaters:
x(int): The number to search for
nums (list of ints): A list of numbers

Returns:
The position in the list where parameter x occurs or, -1 if x is not in the list.
"""
try:
return nums.index(x)
except:
return -1

In [31]:
nums = [3,1,4,1,2,5]

In [8]:
search(7, nums)

Out[8]:
-1
In [9]:
search(4, nums)

Out[9]:
2

## Sequential Searching¶

In [12]:
enumerate(nums)

Out[12]:
<enumerate at 0x111b94d40>
In [13]:
list(enumerate(nums))

Out[13]:
[(0, 3), (1, 1), (2, 4), (3, 1), (4, 2), (5, 5)]
In [14]:
def search(x, nums):
for i,v in enumerate(nums):
if v == x:
return i

return -1

In [15]:
search(4, nums)

Out[15]:
2
In [16]:
search(7, nums)

Out[16]:
-1
In [20]:
def sequential_search(alist, item):
pos = 0
found = False

if alist[pos] == item:
found = True
else:
pos += 1

return found

In [21]:
sequential_search(nums, 4)

Out[21]:
True
In [22]:
sequential_search(nums, 7)

Out[22]:
False
In [35]:
def ordered_sequential_search(alist, item):
pos = 0
found = False
stop = False

if alist[pos] == item:
found = True
else:
if alist[pos] > item:
stop = True
else:
pos += 1

return found

In [36]:
sorted_nums = nums.copy()  # shallow copy of alist

In [37]:
sorted_nums.sort()

In [38]:
ordered_sequential_search(sorted_nums, 4)

Out[38]:
True
In [39]:
ordered_sequential_search(sorted_nums, 7)

Out[39]:
False
In [40]:
nums

Out[40]:
[3, 1, 4, 1, 2, 5]
In [41]:
def binary_search(alist, item):
first = 0  # blue ring
last = len(alist)-1  # gold ring
found = False

midpoint = (first+last)//2  # green ring, must be an int for indexing

if alist[midpoint] == item:
found = True
elif alist[midpoint] > item:  # it's in the lower half of our search space
last = midpoint - 1  # move the gold ring one pos lower than mid
elif alist[midpoint] < item:
first = midpoint + 1  # move the blue ring on pos high than mid

return found

In [42]:
binary_search(nums, 7)

Out[42]:
False
In [43]:
binary_search(nums, 4)

Out[43]:
True

## Searching Workshop¶

Objectives:

1. Time linear searching with increasing lists of numbers
2. Time binary searching with increasing lists of numbers
3. Plot the two verify their time complexities (Big-O values)
4. Bonus: binary search using an OrderedList ADT

Name your workshop ws_searching.ipynb and also print as a PDF file as a backup for Gilbert.