Basic Algorithms: Searching and Sorting With easy examples.

An algorithm is a clear, step-by-step recipe for solving a problem, and two of the most common recipes in computing are searching and sorting. Searching means finding whether an item exists in a collection and where it is, like looking up a name in a contacts list. Sorting means arranging the items of a collection in a defined order, such as smallest to largest or A to Z.

These two ideas matter because almost every program works with collections of data. When you type in a search box, filter products by price, or open a sorted playlist, searching and sorting algorithms are doing the work behind the scenes.

Key Concepts

• Linear search: checks each item one by one from the start until the target is found. It works on any list, sorted or not, but it is slow for large lists.
• Binary search: repeatedly looks at the middle item of a sorted list and discards the half that cannot contain the target. Dramatically faster, but sorting is a precondition.
• Time complexity (Big-O): describes how the work grows as the input grows. Linear search is O(n); binary search is O(log n).
• Comparison sorts: methods that order items by comparing pairs — bubble sort, selection sort, insertion sort, merge sort and quick sort. A stable sort keeps the original order of equal items.

How It Works

Binary search looks at the middle element of a sorted list. If it equals the target, you are done; if the target is smaller, repeat on the left half, otherwise on the right half. Each step discards half the remaining items, so a million-item list needs at most about 20 comparisons. Bubble sort instead walks the list repeatedly, swapping neighbours that are out of order, so the largest unsorted item "bubbles" into place each pass — simple, but needing about n squared comparisons. Merge sort splits the list in half, sorts each half, and merges the sorted halves back together, a divide-and-conquer strategy that scales far better.

Worked Example

Search for 23 in the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] using binary search.

1. low = 0, high = 9. Middle index = (0 + 9) / 2 = 4, holding 16. Since 23 > 16, set low = 5.
2. Middle index = (5 + 9) / 2 = 7, holding 56. Since 23 < 56, set high = 6.
3. Middle index = (5 + 6) / 2 = 5, holding 23. Target found.

Just 3 comparisons, where a linear search could have needed 10. That halving effect is why binary search handles a million sorted items in about 20 steps.

Common Misconceptions

• "Binary search works on any list." The list must be sorted first, otherwise discarding halves can throw away the target.
• "Sorting always makes a program faster." Sorting itself costs time; it pays off only when you search or process the data repeatedly afterwards.
• "Bubble sort is fine for real data." Its n-squared growth makes it unusable beyond a few thousand items; production code uses merge sort, quick sort or library sorts.

Real-World Applications

• Databases keep indexes (often B-trees, a cousin of binary search) so queries find rows without scanning whole tables.
• Online stores sort products by price or rating and search catalogues by keyword.
• File managers sort files by name, date or size on demand.

Searching finds things and sorting puts them in order: binary search halves the problem each step but demands sorted data, while merge sort and quick sort handle large lists efficiently. Pick the algorithm that fits your data size and search frequency.