Searching Algorithms

Techniques that help you locate the right data point quickly—from linear scans to binary search and index-assisted lookups.

What is it?

Searching strategies bridge the gap between stored data and user intent. Linear scan is unbeatable for tiny or unsorted collections, binary search crushes large ordered arrays by halving the problem every step, and hash-based lookups skip traversal altogether when you can derive an index from the key. Text-heavy use cases lean on tries or inverted indexes, while path-finding problems (like routing) depend on graph searches such as BFS, DFS, or Dijkstra’s algorithm. Production systems usually layer these ideas: logs are sorted so SREs can binary-search incidents, caches hash session IDs, and security teams run BFS over relationship graphs to flag anomalies. The better you structure the underlying data, the faster every search variant becomes.

Time Complexity

AccessDependent on backing structure

SearchO(log n) with binary search, O(n) linear

InsertionN/A

DeletionN/A

Implementation Example

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

binarySearch([1,3,5,7,9], 7);

Searching Algorithms

Searching Algorithms Deep Dive

Searching strategies determine how fast you can surface the right record once data is stored—linear scans, binary search, and heuristics each shine in different contexts.

?But why does this matter?

Invest in data layout first: the best searching algorithm still degrades if the underlying structure is unsorted or lacks locality.

Visual Flow

How it actually moves

Linear search

O(n)

Scan sequentially; best for tiny or unsorted collections.

Binary search

O(log n)

Divide the sorted space in half each iteration.

Hash lookup

O(1) average

Leverage hashing to avoid traversal entirely.

Binary search (iterative)

Set low = 0 and high = n - 1.

While low <= high: compute mid = low + (high - low) / 2.

If arr[mid] equals the target, return mid.

If arr[mid] is less than the target, move low to mid + 1.

Otherwise move high to mid - 1. Return -1 when the window collapses.

Variants include returning the insertion index (lower/upper bound) or searching rotated arrays.

Watch the best explainer

Binary Search in 4 Minutes

Michael Sambol

Crisp visual proof of why halving the range finds anything in log time.

Finding a song in a vinyl crate

If the records are unsorted, you flip through every one. If they are alphabetized, you can jump halfway, check the label, and decide which side still holds your song.

Real-world analogy

Customer-support CRMs sort tickets by priority so agents binary-search to the oldest unresolved request.

Takeaway

Better structure (sorting, hashing, indexing) transforms search from linear frustration to logarithmic speed.

Practical applications

• E-commerce search bars ranking products by relevance.
• Log aggregation systems finding error signatures within terabytes of text.
• Security incident response scanning indicators of compromise across hosts.

Technical insights

• Binary search assumes sorted data; pairing it with prefix sums or Fenwick trees unlocks range queries.
• Search indexes (tries, BK-trees, inverted indexes) layer domain-specific heuristics on top of base data structures.
• Approximate nearest-neighbor (ANN) search trades accuracy for speed in high-dimensional vectors.

When to reach for it

• Filtering dashboards
• Autosuggest components
• Monitoring/alerting pipelines

Operations Breakdown

Linear search

O(n)

Scan sequentially; best for tiny or unsorted collections.

Binary search

O(log n)

Divide the sorted space in half each iteration.

Hash lookup

O(1) average

Leverage hashing to avoid traversal entirely.

Best practices

• Profile data distribution; branchless binary search reduces mispredictions on modern CPUs.
• Pre-compute indexes (sorted arrays, tries) rather than re-sorting on every query.
• Expose search telemetry—latency percentiles, miss reasons—to guide tuning.

Common pitfalls

• Relying on binary search without maintaining sorted order causes subtle bugs.
• Complex search heuristics degrade quickly without quality signals or relevance feedback.
• Failing to debounce auto-complete search floods your backend with redundant queries.

Every kind of Searching Algorithms

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 5

Linear & Sentinel Search

→ full page

Scan until found. Unbeatable on unsorted or tiny data, and the baseline every other search is measured against.

What to know

No ordering or preprocessing required; works on any iterable.
A sentinel copy of the target at the end removes the bounds check per step.
Branch prediction makes linear scans of small arrays faster than "smarter" searches.

Algorithms to reach for

Linear scan

O(n)

Find in unsorted data, short-circuit on hit

Sentinel search

O(n)

Micro-optimized scan for hot loops

In the wild: grep over a file, finding an element in a small config list, DOM querySelector fallbacks.

Practice problems — hints, approach & solution on their own pages

Missing NumberEasy Find Pivot IndexEasy

Type 2 of 5

Binary Search (and its many faces)

→ full page

Halve a sorted range every step. The real skill is the variants: boundaries, rotated arrays, and searching the answer space itself.

What to know

lower_bound/upper_bound find first ≥ and first > — most bugs are boundary bugs.
Rotated arrays: one half is always sorted; recurse into the half that can contain the target.
Binary search on the answer: guess a value, test feasibility, shrink — Koko eating bananas, split array.
Use lo + (hi − lo) / 2 to dodge overflow in fixed-width languages.

Algorithms to reach for

Classic binary search

O(log n)

Membership in a sorted array (LeetCode 704)

Lower / upper bound

O(log n)

First/last occurrence, insertion points (LeetCode 34)

Rotated-array search

O(log n)

Search after unknown rotation (LeetCode 33)

Binary search on answer

O(n log range)

Min capacity/speed satisfying a predicate (LeetCode 875, 410)

In the wild: Database index seeks, git bisect, autoscaling threshold tuning, version-cutoff finding.

Practice problems — hints, approach & solution on their own pages

Binary SearchEasy Find First and Last Position in Sorted ArrayMedium Search in Rotated Sorted ArrayMedium Koko Eating BananasMedium Split Array Largest SumHard

Type 3 of 5

Jump, Exponential & Interpolation Search

→ full page

Specialized sorted-array searches: jump ahead in blocks, gallop to find a range, or guess position from value distribution.

What to know

Exponential search doubles the bound (1, 2, 4, 8…) then binary-searches — ideal for unbounded streams.
Interpolation search estimates position linearly; O(log log n) on uniform data, O(n) when skewed.
Galloping is how Timsort merges runs of very different sizes efficiently.

Algorithms to reach for

Exponential (galloping) search

O(log i)

Search unbounded/unknown-length sorted data

Interpolation search

O(log log n) avg

Uniformly distributed sorted keys

Jump search

O(√n)

√n block jumps when binary is awkward

In the wild: Timsort’s merge galloping, phone-book style lookups, sparse index probing.

Practice problems — hints, approach & solution on their own pages

Sqrt(x)Easy Arranging CoinsEasy

Type 4 of 5

Ternary Search & Unimodal Optimization

→ full page

When a function rises then falls (or vice versa), two probe points per step shrink the search interval around the peak.

What to know

Requires strict unimodality — plateaus break the comparison logic.
Two midpoints m1, m2 discard the third of the range that cannot hold the optimum.
On integer domains, binary search on the slope is often simpler.

Algorithms to reach for

Ternary search

O(log n)

Maximize/minimize unimodal functions

Peak finding

O(log n)

Any local peak via slope binary search (LeetCode 162)

In the wild: Hyperparameter sweeps, physics trajectory optima, cost-curve minimization.

Practice problems — hints, approach & solution on their own pages

Find Peak ElementMedium Peak Index in a Mountain ArrayMedium

Type 5 of 5

State-Space Search (BFS / DFS / A*)

→ full page

Searching where there is no array at all: states are nodes, moves are edges. Word ladders, sliding puzzles, and route planning all live here.

What to know

BFS guarantees fewest moves when all moves cost the same.
A* adds a heuristic that never overestimates (admissible) to focus the search.
Bidirectional BFS meets in the middle, roughly squaring-rooting the frontier.
The visited set is what keeps exponential spaces tractable.

Algorithms to reach for

BFS over states

O(states · moves)

Fewest transformations (Word Ladder, LeetCode 127)

Bidirectional BFS

~O(√ of BFS)

Meet-in-the-middle frontier reduction

A* with heuristic

heuristic-dependent

Optimal paths expanding far fewer nodes

In the wild: GPS routing, puzzle solvers, robot motion planning, spell-correction suggestions.

Practice problems — hints, approach & solution on their own pages

Open the LockMedium Word LadderHard Minimum Genetic MutationMedium

Signature algorithms

Algorithm

Linear search

Walk through every element until you find a match; unbeatable for unsorted or tiny collections.

Time

O(n)

Space

O(1)

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i += 1) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

Algorithm

Binary search

Halve the search space each iteration. Requires the data to be sorted (or indexable by rank).

Time

O(log n)

Space

O(1)

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

Algorithm

Hash lookup

Use a hash table / dictionary to reach values in near-constant time by key.

Time

O(1) average

Space

O(n)

function hasUser(usersById, id) {
  return usersById.has(id);
}

const map = new Map();
map.set(101, { name: 'Ada' });
console.log(hasUser(map, 101));

Algorithm

Breadth-first search (graph)

Explore neighbors level by level to find the shortest path in terms of edge count.

Time

O(V + E)

Space

O(V)

function bfs(graph, start) {
  const queue = [start];
  const seen = new Set([start]);
  while (queue.length) {
    const node = queue.shift();
    for (const neighbor of graph[node] ?? []) {
      if (!seen.has(neighbor)) {
        seen.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return Array.from(seen);
}

Pseudo Code • Binary search (iterative)

Flow Diagram

Set low = 0 and high = n - 1.
While low <= high: compute mid = low + (high - low) / 2.
If arr[mid] equals the target, return mid.
If arr[mid] is less than the target, move low to mid + 1.
Otherwise move high to mid - 1. Return -1 when the window collapses.

Variants include returning the insertion index (lower/upper bound) or searching rotated arrays.

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}