9.1 Examples of Problems Solved Using Linear and Binary Search
Linear Search
Problem: Search for an element in an array: Given an array of numbers and a target value. Find the index of the target value in the array.
Solution: Use linear search to check each element in the array.
Implementation example:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
# Example usage:
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target)) # Output: 2
Binary Search
Problem: Search for an element in a sorted array: Given a sorted array of numbers and a target value. Find the index of the target value in the array.
Solution: Use binary search to split the array in halves to find the target value.
Implementation example:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example usage:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target)) # Output: 3
9.2 Problems Using Hash Tables to Optimize Search
1. Finding Duplicates in an Array
Problem: Given an array of numbers. Find and return all duplicates in the array.
Solution: Use a hash table to track numbers that have already been encountered. If a number is encountered again, add it to the duplicates list.
Implementation example:
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Example usage
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Output: [2, 4]
2. Finding Pairs with a Given Sum
Problem: Given an array of numbers and a target sum. Find all pairs of numbers that sum up to the target value.
Solution: Use a hash table to store numbers and check if they form a pair with the current number that gives the target sum.
Implementation example:
def find_pairs_with_sum(arr, target_sum):
seen = set()
pairs = []
for num in arr:
complement = target_sum - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
# Example usage
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum)) # Output: [(1, 5), (7, -1), (1, 5)]
9.3 Combined Use of Different Search Methods
In complex problems, it's often necessary to use several search methods to achieve the best efficiency. Combining linear search, binary search, and hash tables allows for more efficient and flexible problem-solving.
Example 1: Searching for an Element in an Array and Checking its Existence in Another Array
Given two arrays of numbers. Find elements of the first array that exist in the second array.
Solution:
- Use a hash table to store elements of the second array.
- Check each element of the first array for existence in the hash table.
Implementation example:
def find_common_elements(arr1, arr2):
hash_table = set(arr2) # Hash table for the second array
common_elements = []
for element in arr1:
if element in hash_table:
common_elements.append(element)
return common_elements
# Example usage:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2)) # Output: [3, 4, 5]
Example 2: Checking if a Subarray is an Anagram Using a Hash Table
Given an array of strings and a pattern string. Check if any substring of the array of strings is an anagram of the pattern.
Solution:
- Use a hash table to count the frequency of characters in the pattern.
- Traverse the array of strings and use a "sliding window" to check each substring against the character frequencies.
Implementation example:
from collections import Counter
def is_anagram(s1, s2):
return Counter(s1) == Counter(s2)
def find_anagram_substring(arr, pattern):
pattern_length = len(pattern)
pattern_count = Counter(pattern)
for i in range(len(arr) - pattern_length + 1):
substring = arr[i:i + pattern_length]
if is_anagram(substring, pattern):
return True
return False
# Example usage:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern)) # Output: True
9.4 Practical Exercises to Reinforce Material
Exercise 1: Search for an Element in an Unsorted Array
Given an array of numbers and a target value. Find the index of the target value in the array. Use linear search.
Example:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
# Example usage:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target)) # Output: 2
Exercise 2: Finding Duplicates in an Array
Given an array of numbers. Find and return all duplicates in the array using a hash table.
Example:
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Example usage:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr)) # Output: [3, 1]
GO TO FULL VERSION