Skip to content

Searching Algorithms Deep Dive

Implement and analyze linear search, binary search, and hash-based search with their trade-offs.

What you'll learn

  • Linear search: O(n) on unsorted data
  • Binary search: O(log n) on sorted data
  • Interpolation search for uniformly distributed data
  • When to use each search strategy

Concept

Searching Algorithms Deep Dive

Searching is the problem of finding a target value in a collection. The algorithm you choose depends critically on whether the data is sorted and how often you search.

Linear Search

Linear search checks each element one by one. It works on any data and runs in O(n). It is optimal for unsorted data.

Binary Search

Binary search requires sorted data. It repeatedly halves the search range, giving O(log n) time. For n = 1,000,000, that is about 20 comparisons instead of 1,000,000. The key insight: each comparison eliminates half the remaining elements.

Interpolation Search

When data is sorted AND uniformly distributed, interpolation search estimates the target position (like looking up a name in a phone book). It achieves O(log log n) on uniform data but degrades to O(n) on clustered data.

Hash-Based Search

A hash table gives O(1) average lookup but requires O(n) extra space. It is the best choice when you search repeatedly and can afford the memory. The trade-off: hash tables do not support ordered traversal.

Choosing a Strategy

Unsorted single search -> linear; sorted repeated -> binary; repeated lookups -> hash table; sorted uniform -> interpolation.

Example

              // Linear search - works on any array
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}
// Binary search - requires sorted array
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
const sorted = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log('Linear:', linearSearch(sorted, 13));
console.log('Binary:', binarySearch(sorted, 13));
console.log('Not found:', binarySearch(sorted, 14));
            

Linear search scans every element. Binary search halves the range each iteration, requiring the array to be sorted. Both return the index or -1 if not found.

Try it

  • JSON Formatter

    Search through formatted JSON structure to understand how search applies to nested data.

Common mistakes

The mistake

Using binary search on unsorted data.

The fix

Binary search requires sorted data. If the array is not sorted, the halving logic is invalid and you get wrong results.

The mistake

Integer overflow in mid calculation.

The fix

Use (lo + hi) >> 1 or lo + ((hi - lo) >> 1) instead of (lo + hi) / 2 to avoid overflow in languages with fixed-size integers.

Look up unfamiliar terms

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors