Searching Algorithms: Finding Needles in Haystacks

Open your phone's contacts app and type the first two letters of a friend's name. The right contact appears almost instantly, even if you have 800 people saved. Now imagine a CBSE board exam centre with 3,000 answer sheets piled in random order, and an invigilator has to find the sheet belonging to roll number 18114032. If the pile has never been arranged in any order, the invigilator has no choice but to pick up sheet after sheet and check the roll number on each one, until the right sheet turns up — possibly the very last one in the pile. These two situations — searching in a phone's sorted contact list versus searching an unsorted stack of papers — are the same computational problem solved by two completely different strategies. This chapter is about that problem: given a collection of items and a target value, how do we find it, and how do we find it fast? This is the subject of searching algorithms, and it is one of the oldest, most practical ideas in computer science — every database query, every "Ctrl+F", every IRCTC PNR lookup depends on it.

The Baseline Strategy: Linear Search

Suppose you're helping a friend find their roll number's marks on a printed CBSE result sheet — a plain list, not sorted by roll number, just printed in the order the teacher entered them. There is exactly one honest way to do this: start at the top, read each entry, and stop when you find the one you're looking for. If it isn't there at all, you only know that once you've checked every single entry. This is called linear search (also called sequential search), and it is the most basic searching algorithm there is — it makes no assumptions whatsoever about how the data is arranged.

Let's write it precisely. Given an array (a numbered list) arr and a value target we are hunting for, linear search checks each position, one after another, from the first to the last:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i          # found it — return the position
    return -1                 # never matched — not in the list

Let's trace it by hand, because tracing — not just reading — is how you actually understand an algorithm. Take arr = [72, 15, 98, 43, 61] and search for target = 43:

• i = 0: is arr[0] = 72 equal to 43? No.
• i = 1: is arr[1] = 15 equal to 43? No.
• i = 2: is arr[2] = 98 equal to 43? No.
• i = 3: is arr[3] = 43 equal to 43? Yes — return 3.

The function returns 3, the index (position) where 43 lives. It took four comparisons to find an answer in a five-element list. Here is the diagram of exactly this search happening, cell by cell:

Notice the last box, 61, is never even looked at — the search stops the instant it finds a match. That's an important property: linear search's best case is a single comparison (if the target happens to sit at index 0), and its worst case is checking every element (if the target is last, or absent entirely). On average, across many random searches, you'd expect to check about half the list. Computer scientists summarise this worst-case behaviour with a shorthand: linear search takes O(n) comparisons, where n is the number of elements — read this as "the number of steps grows in direct proportion to the size of the list." Double the list, and in the worst case you double the work. There is nothing wrong with linear search — it's simple, it works on any list in any order, and for small lists (say, under a few hundred items) the difference barely matters. Its limitation shows up only when n gets large.

A Smarter Way — But Only If the List Is Sorted

Here's a different, very old game: think of a whole number between 1 and 100. I will guess it, and after each guess you'll only tell me "higher" or "lower." My best strategy is not to guess 1, then 2, then 3 — that's linear search in disguise, and could take up to 100 guesses. My best strategy is to guess 50 first. If you say "higher," I now know the number is somewhere in 51–100 — I've eliminated half the possibilities with a single guess. I guess 75 next, and again I cut whatever remains in half. This halving strategy finds any number from 1 to 100 in at most seven guesses — compare that to up to 100 guesses for checking one by one.

This is exactly the idea behind binary search. The catch — and it is a strict, non-negotiable catch — is that this trick only works because the numbers 1 to 100 are in a known, sorted order. If I told you "guess a number from a jumbled bag of 100 index cards," you'd have no way to know whether 50 is "too high" or "too low," because there's no order to compare against. Sorted order is what makes "higher/lower" meaningful, and that's what binary search depends on completely.

Think of a printed dictionary. To find the word "kilobyte," you don't start at page 1 and read every word. You flick the book open near the middle — say you land on "M" — and since "kilobyte" comes before "M" alphabetically, you know to search only the first half of the book. You repeat this, each time narrowing the region by half, until you land on the right page. A sorted array is just a dictionary made of numbers (or roll numbers, or names) instead of words, and binary search is that exact page-flipping strategy, made precise.

Binary Search, Formally

Binary search keeps track of a search window using two pointers, low and high, which mark the first and last index still worth checking. At each step it looks at the middle index of that window, compares the value there to the target, and shrinks the window to whichever half could still contain the target:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid                # found it
        elif arr[mid] < target:
            low = mid + 1             # target must be in the right half
        else:
            high = mid - 1            # target must be in the left half
    return -1                          # window is empty — not present

Let's trace this on real data. Suppose a CBSE class teacher has sorted 15 students' roll numbers for a merit list: [12, 19, 23, 31, 38, 45, 52, 60, 67, 74, 81, 89, 93, 97, 101], stored at indices 0 through 14, and we're searching for roll number 67.

1. Step 1: low = 0, high = 14. mid = 0 + (14 − 0) // 2 = 7. arr[7] = 60. Since 60 < 67, the target must be to the right, so low becomes 8.
2. Step 2: low = 8, high = 14. mid = 8 + (14 − 8) // 2 = 11. arr[11] = 89. Since 89 > 67, the target must be to the left, so high becomes 10.
3. Step 3: low = 8, high = 10. mid = 8 + (10 − 8) // 2 = 9. arr[9] = 74. Since 74 > 67, high becomes 8.
4. Step 4: low = 8, high = 8. mid = 8. arr[8] = 67. Match — return index 8.

Four comparisons found roll number 67 among 15 entries. A linear search checking indices 0 through 8 in order would have needed nine comparisons to reach the same answer. The gap looks modest here because 15 is a small list — it becomes dramatic as lists grow, which is the whole point of the next section. Here is the shrinking search window drawn out, aligned under the actual array:

Why Binary Search Is So Much Faster: Doubling and Halving

The key insight is this: every step of binary search cuts the remaining search space exactly in half, regardless of how big the list was to start with. This means the number of steps needed grows extremely slowly as the list grows — this relationship is called logarithmic, written O(log n). You don't need logarithm formulas to feel this in your bones; you just need to see how few times you can cut something in half before only one item remains:

• n = 10 items → at most 4 comparisons (10 → 5 → 2 or 3 → 1)
• n = 100 items → at most 7 comparisons
• n = 1,000 items → at most 10 comparisons
• n = 1,000,000 items → at most 20 comparisons
• n = 10,000,000 items (about 1 crore) → at most 24 comparisons

Compare that last row to linear search: searching a sorted list of 1 crore Aadhaar-linked records one by one could take up to 1 crore comparisons in the worst case, versus roughly 24 for binary search. Doubling the size of the list only adds one more comparison to binary search's worst case, while it doubles linear search's worst case outright. This is why every real database index, every phone contacts app, and every dictionary app relies on some variant of this halving idea (often generalised into tree structures called B-trees) rather than scanning records one at a time.

Correcting a Common Misconception: "Binary Search Works on Any List"

A mistake nearly every student makes the first time they meet binary search is assuming it can be dropped into any array, sorted or not, as a free upgrade over linear search. It cannot. Binary search's entire logic — "if the middle value is smaller than the target, the target must be to the right" — is only true because the array is sorted. Feed binary search an unsorted array and it will confidently discard the wrong half and return the wrong answer, or wrongly report "not found" for a value that's actually present. Try tracing binary_search([45, 12, 89, 23, 67], 23) by hand: mid lands on index 2, value 89. Since 89 > 23, the algorithm discards the right half — but it just discarded index 3, where 23 was hiding, and index 1 (value 12) is now wrongly kept in play. The algorithm will report "not found," which is false. Binary search doesn't fail loudly here; it fails silently, which is far more dangerous. If your data isn't sorted, either sort it first (which itself costs time — typically O(n log n), covered when you study sorting algorithms) or use linear search, which makes no assumptions and is always correct.

A second, subtler misconception: students sometimes conclude binary search is unconditionally "better" and should always be preferred. That's also wrong. If you only need to search a small list once — say, checking whether one of your 5 close friends' names appears in a WhatsApp group of 8 people — the overhead of even thinking about sorting is pointless; linear search finishes in a handful of steps regardless. Binary search earns its keep specifically when the list is large and already sorted and you'll be searching it repeatedly (which is exactly the situation with a merit list, a dictionary, or a database index that gets queried thousands of times after being built once).

A Historical Bug Worth Knowing: How You Compute mid Matters

Look again at the line mid = low + (high - low) // 2 in the code above, rather than the more obvious-looking mid = (low + high) // 2. Both give the same answer mathematically. But in 2006, Google engineer Joshua Bloch wrote a widely read analysis showing that Java's own standard library implementation of binary search, using (low + high) / 2, had contained a bug for nearly a decade: if low and high were both very large numbers, their sum could overflow the maximum value a 32-bit integer can hold, silently wrapping around to a negative number and crashing the search. The fix — computing the midpoint as low + (high - low) / 2 — avoids ever adding two large numbers together. Python's integers don't overflow this way, so this exact bug can't bite you here, but the lesson generalises: a correct-looking formula can hide an edge case that only shows up at scale, which is precisely why tracing algorithms carefully, rather than trusting them by eye, is a genuine skill worth building now.

Practice: Test Yourself

Question 1. Trace linear_search([72, 15, 98, 43, 61], 98) by hand. How many comparisons does it take, and what index is returned?
Answer: Check index 0 (72≠98), index 1 (15≠98), index 2 (98=98, match). It takes 3 comparisons and returns index 2.

Question 2. Given the sorted array [3, 7, 9, 14, 22, 35, 40, 51, 60, 72] (indices 0–9), trace binary_search for target 51. Write out low, high, and mid at each step.
Answer: Step 1: low=0, high=9, mid=4, arr[4]=22, 22 < 51, so low=5. Step 2: low=5, high=9, mid=7, arr[7]=51, match — return index 7. Just two comparisons, because this target happened to land close to the first midpoint.

Question 3. A friend has an unsorted list of 30 cricket scores from an inter-house tournament and wants to know if anyone scored exactly 45 runs. Should they use binary search? Why or why not?
Answer: No — the list isn't sorted, and binary search's halving logic only produces correct results on sorted data. They should use linear search directly, or sort the list first if they plan to run many such lookups later.

Question 4. A telecom company's sorted customer database has 10,000,000 records. Roughly how many comparisons would binary search need in the worst case, and how does that compare to linear search on the same database?
Answer: Since 2²³ = 8,388,608 and 2²⁴ = 16,777,216, ten million records fall between those powers of two, so binary search needs at most about 24 comparisons. Linear search could need up to 10,000,000 comparisons in the worst case — roughly 400,000 times more work.

Summary

Searching means locating a target value inside a collection, and the strategy you should use depends entirely on whether the data is sorted. Linear search checks elements one by one, makes zero assumptions about ordering, and costs up to n comparisons for a list of n items — simple, always correct, but slow at scale. Binary search exploits sorted order by repeatedly comparing against the middle element and discarding half the remaining possibilities, cutting the cost down to about log₂(n) comparisons — roughly 24 steps even for a ten-million-entry sorted list — but it is only valid when the data is actually sorted, and running it on unsorted data produces silently wrong answers rather than an obvious error. Between these two ideas sits a genuine engineering trade-off: sorting data costs time up front, so binary search pays off when a large, stable, sorted list will be searched many times, while linear search remains the right, honest choice for small or unsorted collections. Both algorithms show up in real Indian systems every day — from the moment you type into your phone's contact search to the sorted, indexed records behind a train ticket or a board-exam roll-number lookup — and understanding exactly why one is faster than the other, rather than just that it is, is what separates memorising an algorithm from actually understanding one.