Searching in DSA: Finding Data Fast

Searching is the task of finding whether (and where) a target value lives inside a collection. It is one of the most common operations in all of computing — every database query, autocomplete box, and “find in file” is a search underneath. The whole game is doing it with as little work as possible, and the structure of your data decides how fast you can go.

The two questions a search answers

A search usually answers one of two things:

• Membership: “Is x in this collection?” (true/false)
• Location: “At what index does x appear?” (or -1 if absent)

The same algorithm often answers both — return the index if found, and a sentinel like -1 for “not present”.

The core trade-off: structure buys speed

If your data is an unsorted list, you have no choice but to look at elements one by one until you find the target. That is linear search — O(n) time. There’s no shortcut, because the target could be anywhere.

But if your data is sorted, you can be dramatically smarter: check the middle, and because the data is ordered you instantly know which half to discard. That is binary search — O(log n) time. Halving the search space each step is the single most important idea in this section.

// Unsorted -> must scan (O(n)).  Sorted -> can halve (O(log n)).
bool inUnsorted(const std::vector<int>& a, int x) {
    for (int v : a) if (v == x) return true;   // O(n)
    return false;
}

// Unsorted -> must scan (O(n)).  Sorted -> can halve (O(log n)).
boolean inUnsorted(int[] a, int x) {
    for (int v : a) if (v == x) return true;   // O(n)
    return false;
}

// Unsorted -> must scan (O(n)).  Sorted -> can halve (O(log n)).
function inUnsorted(a, x) {
  for (const v of a) if (v === x) return true; // O(n)
  return false;
}

# Unsorted -> must scan (O(n)).  Sorted -> can halve (O(log n)).
def in_unsorted(a, x):
    for v in a:            # O(n)
        if v == x:
            return True
    return False

For beginners: O(log n) is astonishingly fast. Searching 1,000,000,000 sorted items takes only about 30 comparisons, because each step throws away half of what remains.

A map of this section

This section builds searching from the ground up:

• Linear search — the universal baseline that works on any data.
• Binary search — the O(log n) workhorse for sorted data.
• Binary search variations — lower/upper bound and first/last occurrence.
• The two-pointers technique — sweep a sorted array from both ends or in step.
• Binary search on the answer — search a range of answers, not an array.

When to reach for what

• Tiny or unsorted data, searched rarely: linear search. Simple beats clever.
• Sorted data, searched often: binary search. Sort once (O(n log n)), then every lookup is O(log n).
• Need fast lookup but data isn’t ordered: a hash table gives average O(1) membership — often the best choice when you don’t need ordering.

Going deeper: “Searching” is bigger than scanning arrays. BFS and DFS search graphs; binary search trees keep data searchable as it changes. The intuition you build here — exploit structure to skip work — carries everywhere.

Ready? Start with linear search, then practice on the searching exercises.