This chapter covers the essential searching and sorting algorithms that form the backbone of algorithmic problem solving. Binary Search is the cornerstone searching technique on sorted arrays, achieving O(log n) time by repeatedly halving the search space. The technique extends beyond simple lookup to find insertion points (bisect_left and bisect_right), search in rotated sorted arrays, and even binary search on the answer space when the problem exhibits monotonic properties.
Sorting algorithms present a fascinating trade-off between time complexity, space usage, and stability. Comparison-based sorts like Bubble Sort, Insertion Sort, and Selection Sort run in O(n²) time but use O(1) space, making them useful for small or nearly-sorted data. More sophisticated O(n log n) algorithms like Merge Sort, Quick Sort, and Heap Sort divide and conquer the problem. Merge Sort is stable and predictable but requires O(n) extra space, while Quick Sort averages O(n log n) but can degrade to O(n²) in the worst case.
For specialized data, non-comparison-based sorts like Counting Sort and Radix Sort achieve O(n + k) and O(d × (n + k)) respectively by exploiting numerical properties. Shell Sort generalizes insertion sort with gap sequences. The choice of sorting algorithm often depends on the input characteristics: data size, distribution, stability requirements, and available memory all factor into the decision.