Searching and sorting ideas

Finding and ordering data efficiently is fundamental to computational physics — from locating a particle in a grid to ranking eigenvalues.

Linear search — Check every element one by one. Cost: $O(n)$.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Binary search — Requires a sorted array. Repeatedly halve the search space. Cost: $O(\log n)$.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Sorting algorithms

In practice, use Python's built-in sorted() or np.sort(), which use highly optimised $O(n\log n)$ algorithms.

Key insight: Binary search is $O(\log n)$ — searching 1 billion sorted elements takes only about 30 comparisons. But the data must be sorted first.

Common pitfall: Binary search demands sorted input — on unsorted data it fails silently, confidently returning wrong answers. Fast algorithms usually buy their speed with preconditions; know what you promised.

Algorithmic Complexity

The efficiency of a sorting algorithm is measured by comparisons as a function of input size $n$.

• $O(n^{2})$ algorithms (bubble sort, insertion sort) compare every pair.
• $O(n \log n)$ algorithms (merge sort, quicksort) use divide-and-conquer.

The lower bound for comparison sorting is $\Omega(n \log n)$ — no comparison-based algorithm can do better.

Choosing the right algorithm can mean the difference between seconds and hours on large datasets.