5.4 Practice Problems

Problem 1: Linear Search

Write a Python function to implement a linear search algorithm. The function should take a list and the target value as parameters and return the index of the target value if it is in the list, otherwise return -1.

Solution:

def linear_search(lst, target):    for i in range(len(lst)):        if lst[i] == target:            return i    return -1

Problem 2: Binary Search

Implement a Python function for a binary search. The function should take a sorted list and the target value as parameters. If the target value is in the list, return its index. Otherwise, return -1.

Solution:

def binary_search(lst, target):    left, right = 0, len(lst) - 1    while left <= right:        mid = (left + right) // 2        if lst[mid] == target:            return mid        elif lst[mid] < target:            left = mid + 1        else:            right = mid - 1    return -1

Problem 3: Hashing

Suppose you have implemented a hash table with chaining to handle collisions. Now, you are given the keys: 10, 22, 31, 4, 15, 28, 17, 88, 59. Write a Python function to build the hash table using the hash function key mod 10.

Solution:

def build_hash_table(keys):    hash_table = [[] for _ in range(10)]  # Initialize hash table as a list of empty lists    for key in keys:        hash_key = key % 10  # Compute hash key        hash_table[hash_key].append(key)  # Insert key into appropriate bucket    return hash_table keys = [10, 22, 31, 4, 15, 28, 17, 88, 59]print(build_hash_table(keys))

Problem 4: Binary Search vs Linear Search

Given a list of 1000 elements, at what point (number of elements) does it become faster to use a binary search rather than a linear search? Explain your reasoning.

These problems should help you practice what you have learned about search algorithms. The solutions to the problems are in the next section. As always, I would encourage you to try the problems first before looking at the solutions. Happy coding!

In the next chapter, we will dive deeper into sorting algorithms, which are another fundamental aspect of algorithmic thinking. I hope you're excited to continue on this journey!