Topic Overview

Searching Algorithms

Master searching algorithms: linear search, binary search, interpolation search, and their applications in coding interviews.

Searching is the process of finding a specific element in a data structure. Understanding different searching algorithms and their trade-offs is essential for efficient problem-solving.

Why This Matters in Interviews

Searching algorithms are fundamental because:

  • Binary search: Appears in many interview problems (search in rotated array, find peak, etc.)
  • Optimization: Many problems can be solved by reducing search space
  • Complexity analysis: Understanding O(log n) vs O(n) trade-offs
  • Problem patterns: Search problems test your ability to handle edge cases

Interviewers use searching problems to assess your understanding of time complexity, your ability to work with sorted data, and your problem-solving approach.

Core Concepts

  • Linear search: Sequential search through elements
  • Binary search: Divide-and-conquer on sorted data
  • Interpolation search: Optimized for uniformly distributed data
  • Search space reduction: Narrowing down possibilities
  • Search in rotated arrays: Handling special cases
  • Lower/upper bounds: Finding insertion points

Detailed Explanation

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

// Time: O(n)
// Space: O(1)
// Works on: Any data structure, sorted or unsorted

Iterative:

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

// Time: O(log n)
// Space: O(1)
// Requires: Sorted array

Recursive:

function binarySearchRecursive(
  arr: number[], 
  target: number, 
  left: number = 0, 
  right: number = arr.length - 1
): number {
  if (left > right) return -1;
  
  const mid = Math.floor((left + right) / 2);
  
  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

// Time: O(log n)
// Space: O(log n) - recursion stack

Lower Bound (First occurrence):

function lowerBound(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return left;
}

// Returns: First index where target can be inserted

Upper Bound (Last occurrence + 1):

function upperBound(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return left;
}

// Returns: First index where element > target

function interpolationSearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right && target >= arr[left] && target <= arr[right]) {
    // Formula: pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
    const pos = left + Math.floor(
      ((target - arr[left]) * (right - left)) / (arr[right] - arr[left])
    );
    
    if (arr[pos] === target) {
      return pos;
    } else if (arr[pos] < target) {
      left = pos + 1;
    } else {
      right = pos - 1;
    }
  }
  
  return -1;
}

// Time: O(log log n) average (uniform distribution), O(n) worst
// Space: O(1)
// Best for: Uniformly distributed sorted data

Examples

Search in Rotated Sorted Array

function searchRotated(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    }
    
    // Left half is sorted
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return -1;
}

// Time: O(log n)

Find Peak Element

function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] > nums[mid + 1]) {
      // Peak is in left half (including mid)
      right = mid;
    } else {
      // Peak is in right half
      left = mid + 1;
    }
  }
  
  return left;
}

// Time: O(log n)

Search in 2D Matrix

function searchMatrix(matrix: number[][], target: number): boolean {
  if (matrix.length === 0) return false;
  
  const rows = matrix.length;
  const cols = matrix[0].length;
  let left = 0;
  let right = rows * cols - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midValue = matrix[Math.floor(mid / cols)][mid % cols];
    
    if (midValue === target) {
      return true;
    } else if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return false;
}

// Time: O(log(m * n))

Common Pitfalls

  • Integer overflow: (left + right) / 2 can overflow. Fix: Use left + (right - left) / 2
  • Off-by-one errors: Wrong boundary conditions. Fix: Be consistent with inclusive/exclusive
  • Not handling duplicates: Binary search may return any occurrence. Fix: Use lower/upper bound
  • Unsorted data: Binary search requires sorted data. Fix: Sort first or use linear search
  • Infinite loops: Wrong termination condition. Fix: Use left <= right or left < right consistently
  • Missing edge cases: Empty array, single element. Fix: Add explicit checks

Interview Questions

Beginner

Q: Explain binary search. What are its time and space complexities?

A:

Binary Search:

  • Requirement: Array must be sorted
  • Approach: Divide search space in half at each step
  • Process: Compare target with middle element, eliminate half, repeat

Time Complexity:

  • Best: O(1) - target is middle element
  • Average: O(log n) - eliminates half each iteration
  • Worst: O(log n) - target not found

Space Complexity:

  • Iterative: O(1) - only variables
  • Recursive: O(log n) - recursion stack

Example:

Array: [1, 3, 5, 7, 9, 11, 13]
Target: 7

Step 1: mid = 3, arr[3] = 7 ✓ Found!

Key points:

  • Only works on sorted data
  • Much faster than linear search for large arrays
  • Can be implemented iteratively or recursively

Intermediate

Q: Implement binary search to find the first and last occurrence of a target in a sorted array with duplicates.

A:

function searchRange(nums: number[], target: number): number[] {
  const first = findFirst(nums, target);
  if (first === -1) {
    return [-1, -1];
  }
  const last = findLast(nums, target);
  return [first, last];
}

function findFirst(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      result = mid;
      right = mid - 1; // Continue searching left
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

function findLast(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      result = mid;
      left = mid + 1; // Continue searching right
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

// Time: O(log n)
// Space: O(1)

Alternative using lower/upper bound:

function searchRangeOptimized(nums: number[], target: number): number[] {
  const first = lowerBound(nums, target);
  
  if (first === nums.length || nums[first] !== target) {
    return [-1, -1];
  }
  
  const last = upperBound(nums, target) - 1;
  return [first, last];
}

Senior

Q: Design a search system for a distributed database where data is partitioned across multiple nodes. How do you handle range queries, node failures, and ensure low latency?

A:

class DistributedSearch {
  private nodes: Node[];
  private partitioner: Partitioner;
  private coordinator: Coordinator;
  
  constructor(nodes: Node[]) {
    this.nodes = nodes;
    this.partitioner = new RangePartitioner(nodes.length);
    this.coordinator = new Coordinator(nodes);
  }
  
  async search(target: number): Promise<SearchResult> {
    // Determine which node(s) to query
    const nodeIds = this.partitioner.getNodesForValue(target);
    
    // Query nodes in parallel
    const results = await Promise.allSettled(
      nodeIds.map(nodeId => this.nodes[nodeId].search(target))
    );
    
    // Find successful result
    for (const result of results) {
      if (result.status === 'fulfilled' && result.value !== null) {
        return result.value;
      }
    }
    
    return null;
  }
  
  async rangeQuery(min: number, max: number): Promise<number[]> {
    // Get all nodes in range
    const nodeIds = this.partitioner.getNodesForRange(min, max);
    
    // Query each node for its portion of range
    const promises = nodeIds.map(nodeId => 
      this.nodes[nodeId].rangeQuery(
        Math.max(min, this.partitioner.getMin(nodeId)),
        Math.min(max, this.partitioner.getMax(nodeId))
      )
    );
    
    const results = await Promise.all(promises);
    
    // Merge and sort results
    return this.mergeAndSort(results);
  }
  
  private mergeAndSort(results: number[][]): number[] {
    // K-way merge of sorted arrays
    const heap = new MinHeap<{ value: number; arrayIndex: number; elementIndex: number }>();
    const merged: number[] = [];
    
    // Initialize heap
    for (let i = 0; i < results.length; i++) {
      if (results[i].length > 0) {
        heap.insert({
          value: results[i][0],
          arrayIndex: i,
          elementIndex: 0
        });
      }
    }
    
    // Merge
    while (!heap.isEmpty()) {
      const min = heap.extractMin()!;
      merged.push(min.value);
      
      const nextIndex = min.elementIndex + 1;
      if (nextIndex < results[min.arrayIndex].length) {
        heap.insert({
          value: results[min.arrayIndex][nextIndex],
          arrayIndex: min.arrayIndex,
          elementIndex: nextIndex
        });
      }
    }
    
    return merged;
  }
}

class RangePartitioner {
  private ranges: Array<{ min: number; max: number; nodeId: number }>;
  
  constructor(numNodes: number) {
    // Partition range [0, MAX] across nodes
    this.ranges = this.createRanges(numNodes);
  }
  
  getNodesForValue(value: number): number[] {
    // Find node(s) that contain this value
    // For replication, return multiple nodes
    return this.ranges
      .filter(range => value >= range.min && value <= range.max)
      .map(range => range.nodeId);
  }
  
  getNodesForRange(min: number, max: number): number[] {
    return this.ranges
      .filter(range => !(range.max < min || range.min > max))
      .map(range => range.nodeId);
  }
  
  getMin(nodeId: number): number {
    return this.ranges.find(r => r.nodeId === nodeId)!.min;
  }
  
  getMax(nodeId: number): number {
    return this.ranges.find(r => r.nodeId === nodeId)!.max;
  }
  
  private createRanges(numNodes: number): Array<{ min: number; max: number; nodeId: number }> {
    const MAX = Number.MAX_SAFE_INTEGER;
    const rangeSize = Math.floor(MAX / numNodes);
    const ranges = [];
    
    for (let i = 0; i < numNodes; i++) {
      ranges.push({
        min: i * rangeSize,
        max: i === numNodes - 1 ? MAX : (i + 1) * rangeSize - 1,
        nodeId: i
      });
    }
    
    return ranges;
  }
}

Features:

  1. Range partitioning: Distribute data across nodes
  2. Parallel queries: Query multiple nodes simultaneously
  3. Range queries: Efficiently query across partitions
  4. Failure handling: Use replicas if node fails
  5. Result merging: K-way merge of sorted results

Key Takeaways

  • Linear search: O(n), works on any data, simple implementation
  • Binary search: O(log n), requires sorted data, very efficient
  • Interpolation search: O(log log n) average, best for uniform distribution
  • Lower/upper bounds: Useful for finding insertion points and ranges
  • Search space reduction: Key technique in many algorithm problems
  • Edge cases: Empty arrays, single element, duplicates, rotated arrays
  • Optimizations: Use appropriate algorithm based on data characteristics

About the author

InterviewCrafted helps you master system design with patience. We believe in curiosity-led engineering, reflective writing, and designing systems that make future changes feel calm.