Menu iconMenu iconAlgorithms and Data Structures with Python
Algorithms and Data Structures with Python

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:

  1. A loop that runs n times within a loop that runs m times.
  2. A function that divides a list in half repeatedly until the list is of length 1.
  3. An algorithm that processes each item in a list, and for each item, it checks all other items in the list.

Solutions:

  1. O(n * m)
  2. O(log n)
  3. 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:

  1. A loop that runs n times within a loop that runs m times.
  2. A function that divides a list in half repeatedly until the list is of length 1.
  3. An algorithm that processes each item in a list, and for each item, it checks all other items in the list.

Solutions:

  1. O(n * m)
  2. O(log n)
  3. 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:

  1. A loop that runs n times within a loop that runs m times.
  2. A function that divides a list in half repeatedly until the list is of length 1.
  3. An algorithm that processes each item in a list, and for each item, it checks all other items in the list.

Solutions:

  1. O(n * m)
  2. O(log n)
  3. 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:

  1. A loop that runs n times within a loop that runs m times.
  2. A function that divides a list in half repeatedly until the list is of length 1.
  3. An algorithm that processes each item in a list, and for each item, it checks all other items in the list.

Solutions:

  1. O(n * m)
  2. O(log n)
  3. 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.