Difficulty: Advanced
Searching algorithms are fundamental techniques used to find a specific element within a collection of data. The choice of algorithm depends on whether the data is sorted and the performance requirements of your application.
Linear search is the simplest searching algorithm. It checks each element in the collection sequentially until it finds the target or exhausts all elements. It works on both sorted and unsorted data and has a time complexity of O(n) in the worst case. While straightforward, linear search becomes impractical for very large datasets.
Binary search is a dramatically faster algorithm that works exclusively on sorted data. It repeatedly divides the search space in half by comparing the target with the middle element. If the target equals the middle element, the search is complete. If the target is smaller, the search continues in the left half; if larger, in the right half. This divide-and-conquer approach gives binary search a time complexity of O(log n), making it vastly superior to linear search for large datasets.
Python's standard library provides the bisect module, which implements binary search operations for maintaining sorted lists. The bisect_left and bisect_right functions find insertion points for elements, while insort_left and insort_right insert elements while keeping the list sorted. These functions are implemented in C, making them extremely fast.
In practice, Python offers the 'in' operator for membership testing (which performs linear search on lists and O(1) lookup on sets/dicts), and the index() method on lists. However, understanding how these algorithms work under the hood is essential for interviews and for choosing the right data structure for your specific use case.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
numbers = [4, 2, 7, 1, 9, 3]
print(linear_search(numbers, 7))
print(linear_search(numbers, 5))Linear search checks each element from left to right. It returns the index when the target is found, or -1 if the target is not in the list. Time complexity is O(n).
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
sorted_nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(sorted_nums, 7))
print(binary_search(sorted_nums, 6))
print(binary_search(sorted_nums, 15))Binary search halves the search space each iteration. The array must be sorted. Time complexity is O(log n), which for 1 million elements means at most ~20 comparisons.
import bisect
sorted_list = [1, 3, 5, 7, 9, 11]
pos = bisect.bisect_left(sorted_list, 5)
print(pos)
pos_right = bisect.bisect_right(sorted_list, 5)
print(pos_right)
bisect.insort(sorted_list, 6)
print(sorted_list)bisect_left returns the leftmost position where the element can be inserted to maintain order. bisect_right returns the rightmost such position. insort inserts the element while keeping the list sorted.
def binary_search_recursive(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, high)
else:
return binary_search_recursive(arr, target, low, mid - 1)
nums = [2, 4, 6, 8, 10, 12, 14]
print(binary_search_recursive(nums, 10, 0, len(nums) - 1))
print(binary_search_recursive(nums, 3, 0, len(nums) - 1))The recursive version works identically to the iterative one but uses function calls instead of a loop. Each call narrows the search range by adjusting low or high.
linear search, binary search, bisect module