DS&A

Exercises: Searching Lists

Before attempting these exercises, you should read the post on linear and binary search.

Exercises

1. Add the following print statements to the linear search function as appropriate:
   • print('Searching for the target', repr(target))
   • print('The value at index', i, 'is', repr(value))
   • print('The value equals the target')
   • print('The value does not equal the target')
   • print('The target was not found')
   Using ['the', 'cat', 'sat', 'on', 'the', 'mat'] as the input list, record the output when searching for 'on', 'dog' and 'the'.
   Use the interactive linear search model to check your results.
   
2. Add the following print statements to the binary search function as appropriate:
   • print('Searching for the target', repr(target))
   • print('The range is from', left, 'to', right)
   • print('The value at index', middle, 'is', repr(value))
   • print('The value equals the target')
   • print('The value is less than the target')
   • print('The value is greater than the target')
   • print('The target was not found')
   Using ['all', 'bob', 'can', 'do', 'is', 'nap', 'zzz'] as the input list, record the output when searching for 'is', 'bob' and 'sleep'.
   Use the interactive binary search model to check your results.
   
3. The following Python code defines a class User and creates a list of users:

   class User:
       def __init__(self, id_number, name):
           self.id_number = id_number
           self.name = name
       def __repr__(self):
           fmt = 'User({!r}, {!r})'
           return fmt.format(self.id_number, self.name)
   
   users = [
       User(12, 'Waylon Dalton'),
       User(15, 'Justine Henderson'),
       User(20, 'Abdullah Lang'),
       User(28, 'Marcus Cruz'),
       User(45, 'Thalia Cobb'),
       User(46, 'Mathias Little'),
       User(51, 'Eddie Randolph'),
       User(60, 'Angela Walker'),
       User(63, 'Lia Shelton'),
       User(72, 'Hadassah Hartman'),
       User(78, 'Joanna Shaffer'),
       User(95, 'Jonathon Sheppard')
   ]

   It is required to search for users either by name or by ID number.
   1. Write a function using the linear search algorithm to search by name.
   2. The list is ordered by ID number. Write a function using the binary search algorithm to search by ID number.
   Your functions should return the User object found by the search, or None if the search is unsuccessful.

• Tags: 
• exercises, linear search, binary search, lists, search, algorithms

Comments

Aston Walker25 March, 2019Finally completed a lab and understood the work in class. Reading the notes the night before was a great help and this has been my practice for a while. A lot more confident typing code and solutions. The interesting part is being thrown in the deep end at the start of the module as this really assisted with the thought process of thinking about the code. Stish did a really good job!