# Searching¶

In :
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 :
nums = [3,1,4,1,2,5]

In :
search(7, nums)

Out:
-1
In :
search(4, nums)

Out:
2

## Sequential Searching¶

In :
enumerate(nums)

Out:
<enumerate at 0x111b94d40>
In :
list(enumerate(nums))

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

return -1

In :
search(4, nums)

Out:
2
In :
search(7, nums)

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

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

return found

In :
sequential_search(nums, 4)

Out:
True
In :
sequential_search(nums, 7)

Out:
False
In :
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 :
sorted_nums = nums.copy()  # shallow copy of alist

In :
sorted_nums.sort()

In :
ordered_sequential_search(sorted_nums, 4)

Out:
True
In :
ordered_sequential_search(sorted_nums, 7)

Out:
False
In :
nums

Out:
[3, 1, 4, 1, 2, 5]
In :
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 :
binary_search(nums, 7)

Out:
False
In :
binary_search(nums, 4)

Out:
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.