Searching and sorting ideas

Searching Data

Finding data efficiently is fundamental in computational physics, from grid tracking to sorting eigenvalues.

Linear search checks every element sequentially. Cost: $O(n)$.

Binary search repeatedly halves the search space. Cost: $O(\log n)$. For 1 billion sorted elements, it takes only about 30 comparisons.

Common pitfall: Binary search demands sorted input. On unsorted data, it fails silently and returns wrong answers. Fast algorithms buy speed with preconditions.

Sorting Algorithms

The efficiency of sorting is measured by comparisons relative to input size $n$. The lower bound for comparison sorting is $\Omega(n \log n)$.

• $O(n^{2})$ algorithms compare every pair.
• $O(n \log n)$ algorithms use divide-and-conquer.

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