Array Searching

This module explores the core principles of Array Searching, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

Searching is the process of finding a specific element in an array.

Linear Search iterates through the array from start to end, checking each element.

  • Time Complexity: O(N)
  • Space Complexity: O(1)
  • Condition: Works on any array (sorted or unsorted).
public int linearSearch(int[] nums, int target) {
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] == target) {
      return i;
    }
  }
  return -1;
}

Binary Search is a much faster algorithm but requires the array to be sorted. It repeatedly divides the search interval in half.

  • Time Complexity: O(log N)
  • Space Complexity: O(1) (Iterative)
  • Condition: Array must be sorted.

We cover Binary Search in depth in Module 10: Sorting & Searching.

public int binarySearch(int[] nums, int target) {
  int left = 0, right = nums.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}
Ready to search. Enter a target and click Step Search.

3. Deep Dive Strategy Lab: Array Searching

Intuition Through Analogy

Think of this chapter like organizing items on a warehouse shelf. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?

If you are looking for a specific box in an unsorted warehouse, you have no choice but to check every single aisle (Linear Search). However, if the warehouse manager sorted all the boxes by serial number, you could go straight to the middle aisle. If your target serial number is lower than the boxes in the middle, you instantly know to ignore the entire right half of the warehouse (Binary Search). This eliminates half the remaining work at every step.

4. Case Study: The Autocomplete Cache (PEDALS Framework)

Let’s apply these searching concepts to a real-world scenario using the PEDALS framework.

Scenario: You are building a localized, fast-access cache for an autocomplete search bar on a mobile application. The cache holds 10,000 frequently searched, alphabetically sorted strings. When a user types a prefix, the app must quickly determine if the exact string exists in the cache to save a network round-trip.

Process Requirements

  • Input: A target string (e.g., "system design").
  • Output: Boolean (exists or not).
  • Constraint: Must execute in under 1 millisecond on low-end mobile hardware to prevent UI stutter.

Estimate

  • Data Size: 10,000 strings.
  • Memory: Negligible for modern devices, but CPU cycles are precious for battery life.

Data Model

  • A flat, contiguous Array of Strings in memory: ["api", "architecture", "array", ..., "system design"].

Architecture (Algorithmic Choice)

We have a sorted array.

  • Option A: Linear Search. Checking 10,000 strings one by one in the worst case might cause a noticeable lag, especially if string comparison is slow.
  • Option B: Binary Search. We can find any string in log2(10000) ≈ 14 comparisons.

Localized Details

We implement Binary Search. Since strings are sorted lexicographically, we use standard string comparison (compareTo in Java or </> in JS/Python). 14 comparisons vs 10,000 comparisons is the difference between a buttery-smooth 60fps UI and a jarring lag spike.

Scale

If the dataset grows to 1,000,000 items, Linear Search takes 1,000,000 steps. Binary Search takes just ≈ 20 steps. This logarithmic scaling is why keeping data sorted for read-heavy operations is a fundamental architectural pattern.