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
    
    while pos < len(alist) and not found:
        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
    
    while pos < len(alist) and not found and not stop:
        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
    
    while first <= last and not found:
        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.