Searching Algorithms: The Complete Beginner to Advanced Guide

You do this dozens of times a day without thinking about it. You type a name into your phone's contact list. You hit Ctrl+F on a long page to jump to one word. You ask Google Maps for the fastest way home. Every one of those is a searching problem and every one of them is solved by an algorithm that someone had to actually design, because "just look through everything" stops being good enough the moment the amount of data gets large.

That's the whole story of searching algorithms, really. It's not about memorizing a list of names for an exam. It's about one very practical question that shows up constantly in real software: given some data and a value you're looking for, what's the fastest, most reliable way to find it? The answer changes depending on how the data is organized, how often you'll search it and how much you can prepare in advance. This guide walks through that whole landscape, from the simplest possible approach up to the techniques powering databases and interview questions, with tested code and real incidents along the way.

Key takeaways, if you're skimming:

• A searching algorithm finds a value inside data (or proves it isn't there). Which one is "best" depends entirely on how the data is organized and how often you'll search it.
• Binary search is the one to know cold: O(log n), but it only works on sorted data.
• Hashing gives O(1) average lookups but gives up ordering and range queries completely.
• "Average case" is a statement about typical input, not a guarantee , a fact that caused a real, publicly documented security incident, covered later in this guide.
• Real databases don't use plain Binary search internally. They use B-Trees, a structure built specifically for data sitting on disk.

What Is a Searching Algorithm?

A searching algorithm is a step-by-step method used to find a specific value in a collection of data, or determine that the value does not exist. The collection could be an array, linked list, tree, hash table, or even a database containing millions of records. The definition itself is simple. What makes searching interesting is that there are many different ways to find the same piece of data, and the right approach depends on how the data is organized. Searching sequentially through an unsorted list may be perfectly fine for a small collection, while a sorted or indexed data structure can find the same value much more efficiently when the dataset is large.

In other words, the way data is organized often determines how efficiently we can search it.

Why This Actually Matters (Beyond Passing a DSA Course)

Before looking at the different searching algorithms, consider a simple example. Imagine a library with one million books, all shelved in completely random order, and you need to find one specific book. With no useful ordering, you may have to check the books one by one. On average, you would examine around 500,000 books before finding the one you want.

Now arrange the same million books alphabetically by title. Instead of starting from the first book, you can open the library roughly in the middle, determine whether your book comes before or after that point, and eliminate half of the remaining books. Repeat the process, and the search space keeps getting cut in half. You need only around 20 comparisons to narrow down a million possibilities.

That's the fundamental difference between linear search and Binary search. The important lesson isn't simply that Binary search is faster. It's that the way data is organized can allow an algorithm to eliminate huge portions of the search space instead of checking every element individually.

This matters in real software too. A search operation that runs thousands or millions of times can become a significant performance bottleneck if the wrong approach is used. Choosing an appropriate searching algorithm can turn an operation that becomes increasingly expensive as data grows into one that remains fast enough to be practically unnoticeable.

Types of Searching Algorithms: The Big Families You Should Know

Before diving into individual searching algorithms, it helps to understand the broader categories they belong to. Most searching techniques can be grouped into a few families, and knowing the family gives you a good idea of how the search works, what assumptions it makes, and where it is useful.

1. Sequential search

Check elements one by one until the required value is found or there are no elements left to check. It does not require the data to be sorted and works with almost any linear collection. Linear search is the simplest example, with a worst-case time complexity of O(n).

2. Divide-and-conquer search

Reduce the search space by using information about the data to eliminate large portions of it after each comparison. Binary search is the most well-known example and requires sorted data. Other techniques, such as jump search, interpolation search, exponential search, and Fibonacci search, use different strategies to reduce the number of elements that need to be examined.

3. Hash-based search

Use a hash function to map a key to a location in a hash table, allowing the system to find the corresponding value without scanning the collection. Hash tables, dictionaries, and HashMap implementations use this approach. With a good hash function and appropriate sizing, lookup is typically O(1) on average, although the worst case can be O(n).

4. Tree and graph-based search

Search through data organized as connected structures rather than a simple flat collection. Trees such as Binary search trees, balanced trees, and B-Trees can support efficient lookups, while graph-search algorithms such as BFS and DFS explore relationships between connected nodes. These techniques are widely used in databases, file systems, networks, and pathfinding.

The important point is that there is no single "best" searching algorithm. The structure and properties of the data determine which approach makes sense.

Time Complexity (Just Enough to Follow This Article)

If this is new to you, here's the only background you actually need. Big-O notation describes how the amount of work an algorithm does grows as the amount of data grows, independent of hardware or programming language.

• O(n) means the work grows in direct proportion to the data size n: twice the data, roughly twice the work.
• O(log n) means the work grows extremely slowly as data grows. Even if n goes from a thousand to a billion, log n barely increases, because each step eliminates a large fraction of what's left.
• O(1) means the work stays constant no matter how much data there is.

You'll also see three flavors of complexity for each algorithm: the best case (the luckiest possible scenario, like finding the target on the very first check), the average case (what typically happens across many searches) and the worst case (the unluckiest scenario and usually the one that matters most for reliability, since production traffic doesn't ask permission before hitting it).

Searching Algorithms

1. Linear Search: The Obvious Starting Point

Linear search, also called sequential search, checks every element one at a time, in order, from the start, until it finds a match or reaches the end. No cleverness, no precondition about the data being sorted.

Real-life example: You're looking for your friend's name in a group photo caption where names are listed in no particular order. You read left to right, name by name, until you find it. There's no shortcut available, because there's no structure to exploit.

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1  # not found

# Example
names = ["Riya", "Karan", "Deepak", "Priya", "Zoya"]
print(linear_search(names, "Priya"))   # 3
print(linear_search(names, "Neha"))    # -1

• Time complexity: best case O(1) (target is the first element), average and worst case O(n) (you might check every single element).
• Space complexity: O(1); it needs no extra memory beyond the loop itself.
• When to use it: small, unsorted data that you're only going to search once or twice, where sorting first would cost more than the search itself.
• When not to use it: any time the same, reasonably large dataset gets searched repeatedly , at that point it's almost always worth investing in a better structure first.

2. Binary search: The One That Changes Everything

Binary search finds a target in a sorted collection by repeatedly checking the middle element and eliminating half of the remaining range based on whether the target is smaller or larger. Each step throws away half of what's left, which is exactly why it's so fast.

The one hard requirement: The data must already be sorted. This isn't a minor detail. It's the entire reason Binary search works and it's also the source of one of the most common real bugs people write, which we'll get to shortly.

Real-life example: This is exactly how you'd search a physical dictionary or phone book. You don't start at the letter A. You open it somewhere near the middle, see whether your word comes before or after that page and repeat, throwing away half the book each time. If you've ever played the number-guessing game where someone picks a number between 1 and 100 and tells you "higher" or "lower" after each guess, you've already played Binary search, the optimal strategy is always to guess the middle of the remaining range.

Let's walk through it step by step, on a real array:

Binary search on a sorted array, looking for 23

index:    0    1    2    3    4    5    6    7    8
value:  [ 2,   5,   8,  12,  16,  23,  38,  45,  56 ]

Step 1: low=0, high=8, mid=4  -> value at mid = 16
        16 < 23, so search the RIGHT half (low = mid + 1)

index:                        4    5    6    7    8
value:                     [ 16,  23,  38,  45,  56 ]
                                        ^low=5, high=8

Step 2: low=5, high=8, mid=6  -> value at mid = 38
        38 > 23, so search the LEFT half (high = mid - 1)

index:                        5    6
value:                     [ 23,  38 ]
                             ^low=5, high=5

Step 3: low=5, high=5, mid=5  -> value at mid = 23
        23 == 23  -->  FOUND at index 5

3 comparisons to search 9 elements (log2(9) is about 3.2 -- matches)

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2   # see the "classic bug" section below for why
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

arr = [2, 5, 8, 12, 16, 23, 38, 45, 56]
print(binary_search(arr, 23))   # 5
print(binary_search(arr, 99))   # -1

A recursive version works just as well and reads more naturally to some people:

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    mid = low + (high - low) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

• Time complexity: best case O(1), average and worst case O(log n).
• Space complexity: O(1) for the iterative version. O(log n) for the recursive version, because the call stack grows by one frame with each recursive call.

1.Finding the First or Last Occurrence (a Very Common Interview Variant)

Plain Binary search finds any matching index, but real data often has duplicates and a common interview question asks for the first or last position of a value instead. The trick: even after finding a match, keep narrowing in the same direction to check for an earlier (or later) one.

def first_occurrence(arr, target):
    low, high, result = 0, len(arr) - 1, -1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            result = mid
            high = mid - 1     # keep searching the left side for an earlier match
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

dup = [1, 2, 2, 2, 3, 4, 5, 5, 5, 5, 6]
print(first_occurrence(dup, 5))   # 6 (the first 5 is at index 6)
print(first_occurrence(dup, 9))   # -1 (not present)

Most standard libraries already have this built in, so production code rarely needs it written by hand. Python's official bisect module provides bisect_left and bisect_right for exactly this purpose and that's what a real codebase would typically reach for instead.

2.Searching a Rotated Sorted Array (Another Very Common Interview Variant)

A sorted array that's been "rotated" at some pivot point for example [4, 5, 6, 7, 0, 1, 2], which is [0, 1, 2, 4, 5, 6, 7] rotated looks unsorted at a glance, but it still has enough structure for a modified Binary search to work in O(log n). The trick: at every step, figure out which half of the current range is still properly sorted, then check whether the target could possibly be inside that sorted half before deciding which way to move.

def search_rotated(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        if arr[low] <= arr[mid]:            # left half is sorted
            if arr[low] <= target < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:                                # right half is sorted
            if arr[mid] < target <= arr[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))   # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))   # -1
print(search_rotated([6, 7, 0, 1, 2, 4, 5], 4))   # 5

This is a genuinely popular interview question specifically because it forces you to prove you understand why Binary search works (an invariant about ordering), rather than being able to recite the standard version from memory.

3.Binary search on the Answer (An Advanced Technique Worth Knowing)

Binary search doesn't have to search an array at all. It can search a range of possible answers to a problem, as long as the answer has a "yes below this point, no above it" (or the reverse) property. A classic example: finding the integer square root of a number without using a built-in square-root function.

def integer_sqrt(n):
    if n < 2:
        return n
    low, high, ans = 1, n, 0
    while low <= high:
        mid = low + (high - low) // 2
        if mid * mid <= n:
            ans = mid          # mid works; there might be a bigger one that also works
            low = mid + 1
        else:
            high = mid - 1
    return ans

print(integer_sqrt(99))   # 9  (9*9=81 <= 99, 10*10=100 > 99)
print(integer_sqrt(100))  # 10

This same pattern, Binary searching over possible answers instead of over an array, shows up constantly in interview and real optimization problems: "what's the minimum shipping capacity needed to deliver all packages within D days," "what's the smallest square that can contain these items," and similar. If you can write a yes/no check for a candidate answer and the yes/no results are monotonic (all the "no"s on one side, all the "yes"s on the other), you can Binary search it.

The Classic Real Bug: When Binary search Broke at Google

This next story is worth knowing, because it shows why the details of Binary search matter, not just the concept. In 2006, Joshua Bloch, a well-known software engineer who wrote much of Java's core collections library and the book Effective Java, published a piece on the Google Research blog pointing out that the "obvious" way of writing Binary search had a real bug that had gone unnoticed for decades, including in his own previously published code.

The problematic line looked like this:

int mid = (low + high) / 2;

The bug: if low and high are both large enough, their sum can exceed the maximum value a 32-bit integer can hold (about 2.1 billion), causing integer overflow. The sum silently wraps around into a negative number and that negative "middle index" then gets used to access the array throwing an exception in Java or causing undefined, unpredictable behavior in C. This specifically shows up once an array holds roughly a billion or more elements: a size that was impractical when Binary search was first published decades ago, but became realistic in the large-scale systems companies like Google eventually started building. The fix, which is exactly what the code example earlier in this guide already uses, is to compute the midpoint without adding two large numbers directly:

int mid = low + ((high - low) / 2);

The real lesson has nothing to do with that one line of code specifically. It's that a decades-old, extremely well-known algorithm can still hide a real, shipped bug in plain sight and that testing at realistic scale matters even for code that looks obviously correct.

Real-World Usage: git bisect

Binary search shows up as an everyday developer tool too, not just a textbook exercise. Git's git bisect command uses Binary search to find which commit introduced a bug: you give it a known-good commit and a known-bad commit and it checks out the commit exactly in the middle of that range for you to test. Based on whether that commit is good or bad, it discards half the remaining commits and repeats, turning a search through potentially thousands of commits into one that typically finishes in under 20 steps, for exactly the same reason Binary search is fast on a sorted array.

Linear Search vs. Binary search

This exact comparison is one of the most frequently asked questions on this whole topic, so it's worth pulling into its own table.

That last row matters more than it might look. Binary search's speed depends on being able to jump straight to any index in constant time, which arrays support and singly linked lists don't. On a linked list, you'd have to walk node by node just to reach the "middle," which quietly erases the advantage Binary search is supposed to provide.

3. Jump Search: A Middle Ground Between Linear and Binary

Jump search works on sorted data by jumping ahead in fixed-size blocks instead of checking every element, until it jumps past where the target should be, then runs a linear search backward within that one block.

Real-life example: Flipping through a sorted reference book by checking every 10th page instead of every single page and once you've jumped past the section you need, going back and reading normally from there.

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while prev < n and arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    for i in range(prev, min(step, n)):
        if arr[i] == target:
            return i
    return -1

arr = [2, 5, 8, 12, 16, 23, 38, 45, 56]
print(jump_search(arr, 23))   # 5

Why the block size is √n specifically: This isn't an arbitrary choice. If the block size is m, you make at most n/m jumps to find the right block, plus up to m comparisons inside that block, for total work of roughly m + n/m. Basic calculus shows this expression is minimized exactly when m = √n, which is why jump search always sizes its blocks by the square root of the array length.

Time complexity: O(√n), worse than Binary search's O(log n), but better than linear search's O(n). It's a practical choice when jumping backward (which Binary search's halving effectively requires) is more expensive than jumping forward in fixed steps for instance, on storage media where sequential access is cheaper than random access.

4. Interpolation Search: Guessing Smarter, Not Just Splitting in Half

Interpolation search improves on Binary search for sorted, numerically distributed data by estimating where the target is likely to be, rather than blindly checking the middle every time.

Real-life example: This is actually how a human searches a phone book and it's a better analogy for interpolation search than for plain Binary search. If you're looking for "Zebra," you don't open the book in the middle. You jump straight to near the end, because you already know roughly where Z-names live. Interpolation search formalizes that intuition mathematically.

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high and arr[low] <= target <= arr[high]:
        if arr[high] == arr[low]:
            return low if arr[low] == target else -1
        pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1

arr = [2, 5, 8, 12, 16, 23, 38, 45, 56]
print(interpolation_search(arr, 23))   # 5

Time complexity: average case O(log log n) for data that's roughly uniformly distributed, meaningfully faster than Binary search on the right kind of data. There's a real caveat here that often gets left out: if the data isn't uniformly distributed (say, mostly small numbers with a few huge outliers), the position estimate can be consistently wrong and worst-case performance degrades all the way to O(n). That's exactly why interpolation search isn't a universal drop-in replacement for Binary search. Treat it as a specialized tool for data you already know is evenly spread out, like sorted, roughly uniform sensor readings or ID numbers.

5. Exponential Search: For When You Don't Know How Big the Data Is

Exponential search finds a range likely to contain the target by checking positions 1, 2, 4, 8, 16... (doubling each time) until it overshoots the target, then runs a normal Binary search within that bracket.

Real-life example: Scrolling back through an old, unbounded chat history or social media feed to find a specific old message. You don't know how far back it is, so you don't crawl one message at a time. You jump back further and further a day, then a week, then a month and once you've clearly gone too far, you narrow in on the right range.

def exponential_search(arr, target):
    n = len(arr)
    if n == 0:
        return -1
    if arr[0] == target:
        return 0
    i = 1
    while i < n and arr[i] <= target:
        i *= 2
    return binary_search_recursive(arr, target, i // 2, min(i, n - 1))

Time complexity: O(log n). Finding the bracket takes O(log i) steps, where i is the target's actual position and the Binary search inside that bracket takes another O(log i), so the total stays logarithmic. It's especially useful for unbounded or very large sorted sequences where the total size isn't known upfront and for cases where the target tends to be near the beginning, since exponential search reaches it faster than jumping straight to the middle of a huge range would.

6. Ternary Search: Why Splitting into Three Isn't Better

Ternary search divides a search range into three parts using two comparison points. At first glance, this seems better than binary search because each step eliminates roughly two-thirds of the remaining range instead of half.

The catch is the number of comparisons required at each step. Binary search uses one comparison to determine which half may contain the target. Ternary search generally needs two comparisons to determine which of the three sections to continue searching.

Although:

log₃(n) < log₂(n)

ternary search performs more comparisons per iteration. Its comparison count is roughly:

2 × log₃(n) ≈ 1.26 × log₂(n)

So for finding a specific value in a sorted array, binary search is generally more efficient than ternary search.

def ternary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        third = (right - left) // 3

        mid1 = left + third
        mid2 = right - third
        if arr[mid1] == target:
            return mid1
        if arr[mid2] == target:
            return mid2
        if target < arr[mid1]:
            right = mid1 - 1
        elif target > arr[mid2]:
            left = mid2 + 1
        else:
            left = mid1 + 1
            right = mid2 - 1
    return -1


# Example
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90]
target = 70

print(ternary_search(arr, target))

Ternary search is more useful for a different problem: finding the maximum or minimum of a unimodal function : a function that consistently increases up to one point and then consistently decreases, or vice versa.

For example, imagine a function representing the cost of operating a delivery truck at different speeds. At very low speeds, delivery time makes the total cost high. At very high speeds, fuel consumption increases the cost. Somewhere between the two is an optimal speed. If the cost curve is unimodal, ternary search can narrow down that optimum without calculating derivatives.

So the key takeaway is:

For exact-value lookup in a sorted array, binary search is generally the better choice. Ternary search becomes useful when searching for an optimum in a unimodal function.

7. Fibonacci Search: An Honest Look at a Historical Technique

Fibonacci search is a close relative of binary search. It works on a sorted array but uses Fibonacci numbers to decide where to split the search range instead of always dividing it exactly in half. For example, consider:

[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

Instead of calculating the middle index as binary search does, Fibonacci search uses Fibonacci numbers such as 1, 2, 3, 5, 8... to determine its probe positions. After each comparison, it eliminates part of the search range and uses a smaller Fibonacci number to choose the next position.

def fibonacci_search(arr, target):
    n = len(arr)

    # Find the smallest Fibonacci number >= n
    fib2 = 0  # F(k-2)
    fib1 = 1  # F(k-1)
    fib = fib1 + fib2  # F(k)
    while fib < n:
        fib2 = fib1
        fib1 = fib
        fib = fib1 + fib2
    offset = -1
    while fib > 1:
        i = min(offset + fib2, n - 1)
        if arr[i] < target:
            # Target is in the right part
            fib = fib1
            fib1 = fib2
            fib2 = fib - fib1
            offset = i
        elif arr[i] > target:
            # Target is in the left part
            fib = fib2
            fib1 = fib1 - fib2
            fib2 = fib - fib1
        else:
            return i

    # Check the final possible element
    if fib1 and offset + 1 < n and arr[offset + 1] == target:
        return offset + 1
    return -1


# Example
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
target = 70

print(fibonacci_search(arr, target))

Output:

6

Why Was It Useful?

Traditional binary search calculates its midpoint using division:

mid = (left + right) // 2

On older hardware, division was considerably more expensive than simple addition and subtraction. Fibonacci search could determine its probe positions using Fibonacci numbers and avoid division during the search.

That mattered when CPU operations had much larger differences in cost than they do on modern hardware.

Is Fibonacci Search Still Useful Today?

Usually, no.

Modern processors have largely eliminated the practical advantage that motivated Fibonacci search. Binary search is simpler, easier to implement, and widely supported, so it remains the standard choice for most sorted-array lookups.

Fibonacci search is still worth knowing because it demonstrates another way of progressively reducing a sorted search space and occasionally appears in algorithms courses and technical interviews.

Time complexity: O(log n)

Like binary search, Fibonacci search has logarithmic time complexity. The main difference is how it chooses the next position to examine, not the overall complexity class.

In practice: use binary search for most sorted-array lookups. Fibonacci search is mainly useful as an algorithmic concept and a piece of search-algorithm history.

8. Hashing: The Search That Skips Comparisons Entirely

Hashing takes a fundamentally different approach from everything above. Instead of narrowing down a range through comparisons, a hash function converts your search key directly into an array index, so you can jump almost straight to the answer.

An important clarification, because this word gets confused constantly: "hashing" for fast lookups (what this section covers - hash tables, dictionaries, HashMaps) and "hashing" for security (like bcrypt or SHA-256 for storing passwords) both use the word "hash," but they solve different problems with different required properties. A lookup hash function just needs to be fast and spread keys out evenly. A security hash function additionally needs to be practically impossible to reverse or predict. Don't reach for a password-hashing algorithm to build a fast lookup table and don't expect a lookup hash function to protect a password. They're built for different jobs entirely.

Hashing: turning a key into a direct index

   key: "apple"  ---->  hash function  ---->  hash value: 2347
                                                    |
                                             2347 % 10 = 7
                                                    |
                                                    v
   Bucket array (size 10):
   [0] -
   [1] -
   [2] -
   [3] -
   [4] -
   [5] -
   [6] -
   [7] -> ("apple", 1.20) -> ("grape", 2.50)   <-- collision: both hashed to 7
   [8] -
   [9] -

   Lookup "apple": hash it, land on bucket 7, then compare keys
   in that bucket's short chain ("apple" vs "grape") until found.
   Average case: O(1). Worst case (everything collides): O(n).

Real-life example: a coat check at an event. You hand over your coat, get a numbered ticket and when you come back, that number takes the attendant directly to your coat's spot, with no need to search through every coat on the rack. The number is your "hash," computed once at drop-off and used for instant lookup later.

prices = {}
prices["apple"] = 1.20
prices["grape"] = 2.50
prices["banana"] = 0.80

print(prices["apple"])   # 1.2 -- direct lookup, no scanning

Time complexity:

• Average case O(1), staying essentially constant regardless of how much data is stored, as long as the hash function spreads keys out well.
• Worst case O(n), if many keys collide into the same bucket, from a badly chosen hash function or as covered below, a deliberately crafted attack since a bucket in that state degenerates into something you have to search through one item at a time.

A detail worth adding for completeness: Real hash table implementations don't just let buckets fill up forever. They track a load factor (roughly, the number of stored items divided by the number of buckets) and once it crosses a threshold, the table automatically resizes and rehashes everything into a larger bucket array. This is what keeps average-case lookups close to O(1) as a hash table grows, at the cost of an occasional, more expensive O(n) resize operation which, spread out over many insertions, is usually described as amortized O(1) insertion.

The trade-off: hashing gives up ordering entirely. You can't ask a hash table for "everything between X and Y" the way you can with a sorted array or a tree. It only answers "is this exact key here and what's its value."

Real Security Incident: The 2011 Hash-Flooding Denial-of-Service Attacks

What happened next is a well-documented case study in what happens when a searching structure's worst-case behavior stops being theoretical. In December 2011, researchers Julian Wälde and Alexander Klink presented findings at the 28th Chaos Communication Congress showing that many major web platforms, including PHP, ASP.NET, Java's Tomcat server and Ruby (CRuby 1.8), used hash tables with predictable, non-cryptographic hash functions to store incoming web request parameters.

Because the hash function was predictable, an attacker could deliberately craft request data containing many keys engineered to all collide into the same bucket, forcing the hash table into its worst-case O(n) behavior instead of its normal O(1) behavior for every one of those keys. The practical impact was severe: researchers demonstrated that a single connection sending crafted requests could keep thousands of CPU cores busy just parsing that one request, before any of the actual application code had even run. Perl was notably unaffected, because its hash implementation already randomized its hash function per process specifically to prevent this. Following the disclosure, affected platforms rolled out fixes: some capped the number of parameters a request could contain, others limited request size and some replaced their hash tables with balanced trees for parsing untrusted input specifically because a tree's worst case (O(log n)) can't be attacked the same way a hash table's worst case (O(n)) can.

The broader lesson connects directly back to the theory earlier in this guide: average-case complexity is a statement about typical inputs, not a guarantee. If an attacker gets to choose your input and your algorithm has a bad worst case, that worst case is exactly what they'll aim for.

9, Tree-Based Searching: BSTs, Balanced Trees and B-Trees

A Binary search tree (BST) stores data so that for every node, everything smaller lives in its left subtree and everything larger lives in its right subtree. Searching means starting at the root and, at each step, going left or right based on a comparison, narrowing down the search space just like Binary search does, but on a linked structure instead of a flat array.

Searching a Binary search Tree for 35

                         50
                       /    \
                     30      70
                    /  \    /  \
                  20   35  60   80

Step 1: at 50 -- 35 < 50, go LEFT
Step 2: at 30 -- 35 > 30, go RIGHT
Step 3: at 35 -- 35 == 35, FOUND

Only 3 comparisons for 7 nodes, because each step eliminates
an entire half of the remaining tree -- same idea as Binary search,
just on a linked structure instead of a flat array.

This ONLY works this well if the tree is balanced. If nodes were
inserted in already-sorted order (10, 20, 30, 35, 50, 60, 70), the
tree degenerates into a straight line and search becomes O(n),
exactly like a linked list. Self-balancing trees (AVL, Red-Black)
exist specifically to prevent this from happening.

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def bst_search(root, target):
    while root:
        if root.val == target:
            return True
        root = root.left if target < root.val else root.right
    return False

Time complexity: average case O(log n) for a reasonably balanced tree, worst case O(n) for a poorly balanced one, exactly as the diagram above shows. Self-balancing trees, most commonly AVL trees and Red-Black trees, automatically rearrange themselves during insertion and deletion to guarantee O(log n) search even in the worst case, closing the gap a plain BST leaves open.

Real-world usage: B-Trees (and their common variant, B+ Trees) generalize this same idea for data stored on disk rather than in memory. Each node holds many keys instead of just one, which drastically reduces how many slow disk reads a search needs. This is not theoretical: relational databases actually work this way under the hood. PostgreSQL's own documentation describes the B-Tree as its default and most commonly used index type for exactly this reason and MySQL's InnoDB storage engine organizes both primary keys and secondary indexes as B+ Trees. Every time a WHERE clause on an indexed column returns instantly on a table with millions of rows, a B-Tree search is very likely what's happening underneath.

10. Graph Search: BFS and DFS

Once your data is a network of connections rather than a flat list think social connections, road networks or web pages linking to each other. You're searching a graph and the two foundational approaches are breadth-first and depth-first search.

Breadth-First Search (BFS) : Explores level by level, checking all of a node's direct neighbors before moving further out, using a queue to track what to visit next. It's the natural choice when you want the shortest path in terms of number of connections, because it never goes deeper than it needs to before exhausting closer options.

Depth-First Search (DFS) : Dives as deep as possible down one path before backtracking, using a stack (or recursion) instead of a queue. It's the natural choice for exploring every possible path, like solving a maze or for problems where you need to fully explore one branch before considering others.

from collections import deque

def bfs_shortest_distance(graph, start, target):
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C', 'E'],
    'E': ['D'],
}
print(bfs_shortest_distance(graph, 'A', 'E'))   # 3

Real-life example: GPS and mapping applications need to find the shortest route between two points on a road network, which is fundamentally a graph search problem. Algorithms like Dijkstra's algorithm and A* search extend the same core BFS idea (explore outward, track distance) while also accounting for road distances or travel time as weights instead of treating every connection as equal. A feature that shows "you're connected through 2 people" on a social platform is doing exactly what breadth-first search is built for: exploring the friend or follower graph outward, one degree of connection at a time, until it reaches the target.

Time complexity: O(V + E) for both BFS and DFS, where V is the number of nodes (vertices) and E is the number of connections (edges), assuming the graph is stored as an adjacency list, which is the standard representation for sparse, real-world graphs. It's worth knowing this bound changes if a graph is instead stored as an adjacency matrix, where simply checking a single node's neighbors costs O(V), pushing the total search to O(V²) a good reminder that "the algorithm's complexity" and "the data structure backing it" aren't fully separate questions.

Myths About Searching Algorithms, Debunked

A few claims about searching algorithms get repeated so often online that they start to sound like settled fact, even when the real picture is more specific.

Comparison Table: Every Searching Algorithm, Side by Side

• *Average case only and only for roughly uniformly distributed data, degrades toward O(n) otherwise.
• **Same complexity class as Binary search, but with a larger constant factor, see the ternary search section for why it's not actually faster for exact-match search.
• ***Only if the hash function distributes keys poorly or under a deliberate collision attack (see the hash-flooding section above).
• ****Only for an unbalanced tree, self-balancing variants avoid this.

How to Choose the Right Searching Algorithm

Picking the right approach -- walk through these questions in order:

1. Will you search this data only once or is it tiny (a few dozen items)?
   -> Just use LINEAR SEARCH. Sorting first would cost more than it saves.

2. Is the data sorted and will you search it many times?
   -> Use Binary search (array) -- O(log n) per lookup.

3. Do you only need exact key -> value lookups (no ordering, no ranges)?
   -> Use HASHING (a hash table / dictionary / HashMap) -- O(1) average.

4. Do you need range queries ("everything between X and Y") AND the data
   keeps changing (frequent insert/delete)?
   -> Use a SELF-BALANCING TREE (AVL, Red-Black Tree) -- O(log n),
      guaranteed even in the worst case.

5. Is the dataset too large to fit in memory, like a database table on disk?
   -> Use a B-TREE / B+ TREE -- built specifically to minimize slow disk
      reads. This is what MySQL, PostgreSQL and most databases use
      under the hood for their indexes.

There's no single "best" searching algorithm in the abstract, only the best one for a specific combination of data size, how often you'll search it, whether it's sorted, whether it changes over time and whether you need more than exact-match lookups. That's the whole skill of this topic: matching the tool to the actual shape of the problem.

Common Mistakes That Actually Bite People

• Running Binary search on unsorted data. This is the single most common mistake and it's dangerous specifically because it doesn't crash. It just silently returns wrong results or a false "not found," some of the time, which is much harder to catch than a clean error.

• Getting the midpoint calculation wrong at scale. As the Joshua Bloch story above shows, (low + high) / 2 can overflow on very large arrays in languages with fixed-size integers. low + (high - low) / 2 avoids the problem and is worth making a default habit rather than an exception.

• Off-by-one errors in the loop condition. Using low < high instead of low <= high (or the reverse) is a classic way to either miss the last valid element or loop forever. When writing Binary search by hand, it's worth deliberately tracing through a 1-element and a 2-element array to confirm the boundary behaves correctly.

• Assuming average-case complexity is a guarantee. A hash table is O(1) on average, but as the 2011 hash-flooding attacks proved at real scale, "average case" assumes reasonably distributed input, an assumption that quietly breaks if an attacker controls the input.

• Treating ternary search as a faster Binary search. As covered above, it isn't, for exact-match array searching. The math doesn't work out in ternary search's favor once you count actual comparisons, not just levels.

• Reaching for interpolation search on non-uniform data. It can end up slower than Binary search in the worst case if the data's distribution doesn't match the assumption it relies on.

Performance, Scalability and Security Considerations

Performance and scalability

Come down to matching the algorithm to the data's shape and access pattern, which is really the point of the comparison table above. An O(log n) algorithm on a dataset of a billion items still finishes in about 30 comparisons, while an O(n) algorithm on the same data could mean a billion comparisons a difference that's easy to underestimate until you see the actual numbers side by side.

Security

Deserves its own explicit mention because of the hash-flooding story above. Any time a searching structure's worst-case behavior is meaningfully worse than its average case and an attacker can influence the input, that worst case becomes a real attack surface, not just an academic footnote. This is why modern language runtimes randomize their default hash function's seed per process, specifically to stop an attacker from predicting which keys will collide.

Memory trade-offs

Matter too, Hashing and trees both spend extra memory (O(n)) to get their speed, while array-based approaches like Binary search need none beyond the array itself. On memory-constrained systems, that difference can matter as much as raw speed.

Searching Algorithms in Coding Interviews

Searching algorithms are some of the most consistently tested topics in technical interviews, precisely because they reward understanding over memorization. Here's a quick map of well-known problem patterns to the technique behind them and where in this guide each one is covered.

A few things worth being genuinely comfortable with, beyond recognizing the table above: implementing Binary search correctly from scratch, including the first/last occurrence and rotated-array variants, recognizing when a problem is secretly "Binary search on the answer" rather than a normal array search, which usually shows up in phrases like "minimum value such that" or "smallest X where condition holds"; knowing the difference between BFS and DFS well enough to justify picking one over the other for a specific graph problem, not just being able to define both and explaining, out loud and with correct reasoning, why a hash table's O(1) isn't actually guaranteed the way the label makes it sound.

Interviewers are typically far more interested in hearing you reason through trade-offs, such as why Binary search needs sorted data, why hashing gives up ordering or why the worst case matters even when it's rare, than in watching you type out a memorized solution without explaining any of it.

Frequently Asked Questions

1. What is the difference between linear search and Binary search?

Linear search checks elements one at a time and works on any data, sorted or not, taking up to O(n) time. Binary search repeatedly cuts the search space in half but requires the data to already be sorted, taking only O(log n) time, dramatically faster on large datasets at the cost of that sorting requirement.

2. Which searching algorithm is the fastest?

There's no single fastest algorithm for every situation. Hashing is typically fastest for exact-match lookups (O(1) average). Binary search is typically fastest when you need ordering or range queries on sorted data (O(log n)). The "fastest" answer always depends on what the data looks like and what kind of query you actually need.

3. Why must the array be sorted before using Binary search?

Binary search works by comparing the target to the middle element and confidently discarding one entire half of the data, based on the assumption that everything in the discarded half is definitely too small or too large. That assumption is only valid if the data is already ordered. On unsorted data, that conclusion can be wrong and the algorithm can silently return an incorrect result.

4. What is the time complexity of searching algorithms in the worst case?

It depends on the algorithm: linear search is O(n), Binary search and its sorted-array relatives are O(log n) or O(√n), hashing is O(1) on average but O(n) in the worst case and balanced trees or B-Trees guarantee O(log n) even in their worst case. The full comparison table earlier in this guide lists every algorithm covered side by side.

5. Is hashing better than Binary search?

For a pure "does this exact value exist" lookup, hashing is generally faster on average. But hashing can't answer range queries ("everything between X and Y") or provide sorted order, while Binary search and trees can, so "better" depends entirely on what your application actually needs to ask the data.

6. What searching algorithm do real databases use?

Most relational databases index data using B-Trees or B+ Trees specifically because they're optimized for data stored on disk rather than in memory, minimizing the number of slow disk reads a search needs. PostgreSQL and MySQL's InnoDB engine both use this structure for their standard indexes.

The Bottom Line

Every searching algorithm in this guide is really answering the same question in a different context: how do you avoid checking everything, one item at a time? Sorting and comparing gets you Binary search and its relatives. Transforming the key directly into a location gets you hashing. Organizing data as a tree or a graph gets you the structures that power databases and pathfinding. None of them is universally "the best." The real skill, the one that actually shows up in interviews and in production code, is recognizing what shape your data and your queries actually have and picking the tool built for exactly that shape.

Every code example in this guide was run and its output checked against what's shown in the comments, including the rotated-array, first-occurrence and integer-square-root variants. The two historical incidents were checked against primary sources rather than secondhand summaries: Joshua Bloch's original Google Research post for the Binary search overflow bug and the original 2011 hashDoS disclosure writeup for the denial-of-service story. Where a claim depends on a specific product's internals, such as which index structure PostgreSQL or MySQL uses, it's linked to that project's own documentation rather than stated on general impression.

Related Articles

Binary Search Explained: With Real Examples

How to Identify and Approach Two Pointer Problems?

How to Identify and Approach Sliding Window Patterns in DSA

Graph Traversal (DFS and BFS) Explained with Examples

How to Identify and Approach Backtracking Problems

How to Identify and Approach Dynamic Programming Questions

How to Approach Any DSA Interview Problem: Complete Step-by-Step Guide

Real Interview Experiences: Google, Amazon and Meta

The Ultimate Interview Practice Sheet for FAANG Interviews

Sources referenced:

• Nearly All Binary searches and Mergesorts are Broken Google Research
• Effective DoS Attacks Against Web Application Platforms Cryptanalysis.eu (28C3 disclosure summary)
• PostgreSQL Documentation: B-Tree Indexes
• Python Documentation: bisect Array bisection algorithm