Chapter 5: Search Algorithms
5.4 Practice Problems of Chapter 5: Search Algorithms
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 -1Problem 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 -1Problem 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!
5.4 Practice Problems of Chapter 5: Search Algorithms
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 -1Problem 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 -1Problem 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!
5.4 Practice Problems of Chapter 5: Search Algorithms
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 -1Problem 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 -1Problem 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!
5.4 Practice Problems of Chapter 5: Search Algorithms
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 -1Problem 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 -1Problem 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!