Chapter 5: Search Operations & Efficiency
Chapter 5: Practical Exercises of Search Operations & Efficiency
Exercise 1
Implement a function that performs a linear search on a given list.
Input: A list and a target value.
Output: The index of the target value in the list. If the target value is not present, return -1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(linear_search(lst, 5)) # Output: 2
print(linear_search(lst, 6)) # Output: -1
Exercise 2
Implement a binary search function without using recursion.
Input: A sorted list and a target value.
Output: The index of the target value in the list. If the target value is not present, return -1.
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(binary_search(lst, 5)) # Output: 2
print(binary_search(lst, 6)) # Output: -1
Exercise 3
Given the earlier explanation of hashing, implement a basic hash function for strings that distributes characters evenly.
Hint: For simplicity, assume the input string consists of lowercase English letters only, and the hash table size is 100.
def simple_hash(s):
total = 0
for char in s:
total += ord(char) - ord('a') + 1
return total % 100
# Test
print(simple_hash('hello')) # This will give an output between 0 and 99.
Exercise 4
Evaluate the time complexities:
- A loop that runs n times within a loop that runs m times.
- A function that divides a list in half repeatedly until the list is of length 1.
- An algorithm that processes each item in a list, and for each item, it checks all other items in the list.
Solutions:
- O(n * m)
- O(log n)
- O(n^2)
Exercise 5
Reflecting on hashing's efficiency: If we have a hash table of size 100 and 50 entries, what's the load factor? Calculate it.
Solutions:
Load factor = number of entries / size of the table = 50/100 = 0.5 or 50%.
These exercises should give you practical exposure to the concepts introduced in Chapter 5. They are designed to combine both implementation and theoretical questions for a rounded understanding.
Chapter 5: Practical Exercises of Search Operations & Efficiency
Exercise 1
Implement a function that performs a linear search on a given list.
Input: A list and a target value.
Output: The index of the target value in the list. If the target value is not present, return -1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(linear_search(lst, 5)) # Output: 2
print(linear_search(lst, 6)) # Output: -1
Exercise 2
Implement a binary search function without using recursion.
Input: A sorted list and a target value.
Output: The index of the target value in the list. If the target value is not present, return -1.
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(binary_search(lst, 5)) # Output: 2
print(binary_search(lst, 6)) # Output: -1
Exercise 3
Given the earlier explanation of hashing, implement a basic hash function for strings that distributes characters evenly.
Hint: For simplicity, assume the input string consists of lowercase English letters only, and the hash table size is 100.
def simple_hash(s):
total = 0
for char in s:
total += ord(char) - ord('a') + 1
return total % 100
# Test
print(simple_hash('hello')) # This will give an output between 0 and 99.
Exercise 4
Evaluate the time complexities:
- A loop that runs n times within a loop that runs m times.
- A function that divides a list in half repeatedly until the list is of length 1.
- An algorithm that processes each item in a list, and for each item, it checks all other items in the list.
Solutions:
- O(n * m)
- O(log n)
- O(n^2)
Exercise 5
Reflecting on hashing's efficiency: If we have a hash table of size 100 and 50 entries, what's the load factor? Calculate it.
Solutions:
Load factor = number of entries / size of the table = 50/100 = 0.5 or 50%.
These exercises should give you practical exposure to the concepts introduced in Chapter 5. They are designed to combine both implementation and theoretical questions for a rounded understanding.
Chapter 5: Practical Exercises of Search Operations & Efficiency
Exercise 1
Implement a function that performs a linear search on a given list.
Input: A list and a target value.
Output: The index of the target value in the list. If the target value is not present, return -1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(linear_search(lst, 5)) # Output: 2
print(linear_search(lst, 6)) # Output: -1
Exercise 2
Implement a binary search function without using recursion.
Input: A sorted list and a target value.
Output: The index of the target value in the list. If the target value is not present, return -1.
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(binary_search(lst, 5)) # Output: 2
print(binary_search(lst, 6)) # Output: -1
Exercise 3
Given the earlier explanation of hashing, implement a basic hash function for strings that distributes characters evenly.
Hint: For simplicity, assume the input string consists of lowercase English letters only, and the hash table size is 100.
def simple_hash(s):
total = 0
for char in s:
total += ord(char) - ord('a') + 1
return total % 100
# Test
print(simple_hash('hello')) # This will give an output between 0 and 99.
Exercise 4
Evaluate the time complexities:
- A loop that runs n times within a loop that runs m times.
- A function that divides a list in half repeatedly until the list is of length 1.
- An algorithm that processes each item in a list, and for each item, it checks all other items in the list.
Solutions:
- O(n * m)
- O(log n)
- O(n^2)
Exercise 5
Reflecting on hashing's efficiency: If we have a hash table of size 100 and 50 entries, what's the load factor? Calculate it.
Solutions:
Load factor = number of entries / size of the table = 50/100 = 0.5 or 50%.
These exercises should give you practical exposure to the concepts introduced in Chapter 5. They are designed to combine both implementation and theoretical questions for a rounded understanding.
Chapter 5: Practical Exercises of Search Operations & Efficiency
Exercise 1
Implement a function that performs a linear search on a given list.
Input: A list and a target value.
Output: The index of the target value in the list. If the target value is not present, return -1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(linear_search(lst, 5)) # Output: 2
print(linear_search(lst, 6)) # Output: -1
Exercise 2
Implement a binary search function without using recursion.
Input: A sorted list and a target value.
Output: The index of the target value in the list. If the target value is not present, return -1.
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(binary_search(lst, 5)) # Output: 2
print(binary_search(lst, 6)) # Output: -1
Exercise 3
Given the earlier explanation of hashing, implement a basic hash function for strings that distributes characters evenly.
Hint: For simplicity, assume the input string consists of lowercase English letters only, and the hash table size is 100.
def simple_hash(s):
total = 0
for char in s:
total += ord(char) - ord('a') + 1
return total % 100
# Test
print(simple_hash('hello')) # This will give an output between 0 and 99.
Exercise 4
Evaluate the time complexities:
- A loop that runs n times within a loop that runs m times.
- A function that divides a list in half repeatedly until the list is of length 1.
- An algorithm that processes each item in a list, and for each item, it checks all other items in the list.
Solutions:
- O(n * m)
- O(log n)
- O(n^2)
Exercise 5
Reflecting on hashing's efficiency: If we have a hash table of size 100 and 50 entries, what's the load factor? Calculate it.
Solutions:
Load factor = number of entries / size of the table = 50/100 = 0.5 or 50%.
These exercises should give you practical exposure to the concepts introduced in Chapter 5. They are designed to combine both implementation and theoretical questions for a rounded understanding.