Python Search Algorithms

This page collects four classic routines that come up constantly in Python interviews and everyday code: intersecting two lists with sets, binary search over a sorted list, and the two divide-and-conquer sorts, quick sort and merge sort. Each has a short implementation above; the sections below add complexity analysis, traces of how the algorithms move through their input, the standard-library equivalents you should usually reach for, and the mistakes that most often break hand-written versions.

1. Find the Intersection of Two Lists

def list_intersection(list1: list, list2: list) -> list:
    return list(set(list1) & set(list2))

print(list_intersection([1, 2, 3, 4], [3, 4, 5, 6]))  # Output: [3, 4]
The binary search algorithm works by repeatedly dividing the array into two halves until the target element is found or a single element remains. In each iteration, we compare the middle element of the current half with the target element. If they are equal, we return the index of the middle element as the result. If the middle element is less than the target element, we discard the first half of the array and repeat the same process on the second half. Similarly, if the middle element is greater than the target element, we discard the second half of the array and repeat the same process on the first half. 
def binary_search(arr, target):
    low = 0
    high = 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

3. Quick Sort

The quick sort algorithm works by selecting a pivot element from the array and partitioning it into two halves, one containing elements less than or equal to the pivot and another containing elements greater than the pivot. We then recursively call the quick sort function on both halves. 
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

4. Merge Sort

The merge sort algorithm works by dividing the array into two halves, sorting each half recursively and then merging them back together. In the base case, an array of length 1 or less is considered sorted and returned as is. 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result

5. Complexity summary

AlgorithmBestAverageWorstSpace
List intersection (sets)O(n+m)O(n+m)O(n·m)O(n+m)
Binary searchO(1)O(log n)O(log n)O(1)
Quick sortO(n log n)O(n log n)O(n²)O(n) as written
Merge sortO(n log n)O(n log n)O(n log n)O(n)

The worst case for set intersection only occurs with pathological hash collisions; in practice it is linear. The quick sort shown builds new lists at every level, so it uses O(n) extra memory per level of recursion on top of the O(log n) average depth; an in-place partitioning version uses only the recursion stack.

6. Binary search trace

Searching for 23 in a sorted list of 9 items low=0 high=8 mid=4 2 5 8 12 16 23 38 56 72 16 < 23: low=5, mid=6 2 5 8 12 16 23 38 56 72 38 > 23: high=5, mid=5 2 5 8 12 16 23 38 56 72 Each comparison halves the remaining range: 9 -> 4 -> 1 elements

Binary search keeps an interval [low, high] that must contain the target if it exists. Comparing with the middle element discards half of that interval each step, so at most about log2(n) + 1 comparisons are needed: 20 for a million items, 30 for a billion. The precondition is that the list is sorted by the same key you search on; on unsorted input the function returns wrong answers silently rather than failing.

In real code use the bisect module, which implements the same loop in C and returns insertion points rather than just found/not-found:

from bisect import bisect_left

def index_of(a, x):
    i = bisect_left(a, x)
    return i if i < len(a) and a[i] == x else -1

print(index_of([2, 5, 8, 12, 16, 23, 38], 23))  # 5

7. Divide and conquer: quick sort versus merge sort

Two ways to split the work Quick sort partition first, then recurse [3] [1 2] pivot [5 8 9] work done while splitting Concatenate no merge step Merge sort recurse first, then merge [1 3 8] + [2 5 9] work done while combining Merge take smaller head

Both algorithms split the problem in two, but they put the effort in different places. Quick sort does its work up front: partitioning around a pivot places every element on the correct side, after which the halves are sorted independently and simply concatenated. Merge sort splits trivially at the midpoint and does its work afterwards, merging two sorted halves by repeatedly taking the smaller head element.

This difference explains their trade-offs. Merge sort always produces balanced halves, so it is guaranteed O(n log n) and is stable, but it needs O(n) auxiliary space for merging. Quick sort can be done in place and has excellent cache behaviour, but a bad pivot (for example the first element of already-sorted input, as in the version above) produces one empty side and one side of n−1 elements, degrading to O(n²) and recursion depth n. Choosing a random pivot or the median of three makes that case very unlikely. Python's built-in sorted uses Timsort, a merge-sort hybrid that exploits existing runs in the data.

8. Pitfalls