Module 3: Searching

Master the fundamentals of searching algorithms. Learn how to implement and analyze searching algorithms.

Module Objectives

Upon completion of this module you will be able to:

Implement a linear search algorithm and understand its O(n) time complexity
Implement a binary search algorithm and understand its O(log n) time complexity
Compare the efficiency of linear and binary search algorithms
Identify when to use each search algorithm based on data characteristics
Apply search algorithms to solve real-world programming problems

Linear Search

Understanding Linear Search

Linear search is the simplest search algorithm. It sequentially checks each element in a collection until the target is found or the collection is exhausted.

// Linear search implementation
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // Return the index where target is found
    }
  }
  return -1; // Return -1 if target is not found
}

// Example usage
const numbers = [10, 24, 56, 7, 89, 42, 13];
console.log(linearSearch(numbers, 89)); // 4
console.log(linearSearch(numbers, 100)); // -1
  

Time Complexity:

Best Case: O(1) - Element found at the first position
Average Case: O(n) - Element found after checking half the elements
Worst Case: O(n) - Element found at the last position or not found

Space Complexity: O(1) - Uses a constant amount of extra space

Advantages of Linear Search:

Simple to implement
Works on both sorted and unsorted arrays
No pre-processing required
Efficient for small datasets

Disadvantages:

Inefficient for large datasets (O(n) time complexity)
Does not take advantage of sorted data

Optimized Linear Search

We can optimize linear search by adding early termination conditions or implementing search strategies like the sentinel search:

// Linear search with sentinel
function sentinelLinearSearch(arr, target) {
  const n = arr.length;
  
  // Save the last element
  const last = arr[n - 1];
  
  // Place the target as sentinel at the end
  arr[n - 1] = target;
  
  let i = 0;
  // The loop will always terminate because target is in the array
  while (arr[i] !== target) {
    i++;
  }
  
  // Restore the original last element
  arr[n - 1] = last;
  
  // Check if we found the target or just the sentinel
  if (i < n - 1 || last === target) {
    return i;
  }
  return -1;
}
  

Binary Search

Understanding Binary Search

Binary search is a divide-and-conquer algorithm that efficiently finds a target value in a sorted array. It repeatedly divides the search space in half, eliminating half of the remaining elements at each step.

// Binary search implementation (iterative)
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    // Calculate middle index (avoid overflow)
    const mid = left + Math.floor((right - left) / 2);
    
    // Check if target is at mid
    if (arr[mid] === target) {
      return mid;
    }
    
    // If target is greater, ignore left half
    if (arr[mid] < target) {
      left = mid + 1;
    } 
    // If target is smaller, ignore right half
    else {
      right = mid - 1;
    }
  }
  
  // Target not found
  return -1;
}

// Example usage
const sortedNumbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(binarySearch(sortedNumbers, 23)); // 5
console.log(binarySearch(sortedNumbers, 25)); // -1
  

Recursive Binary Search

Binary search can also be implemented recursively:

// Binary search implementation (recursive)
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // Base case: element not found
  if (left > right) {
    return -1;
  }
  
  // Calculate middle index
  const mid = left + Math.floor((right - left) / 2);
  
  // Check if target is at mid
  if (arr[mid] === target) {
    return mid;
  }
  
  // Recursive cases
  if (arr[mid] < target) {
    // Search right half
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    // Search left half
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}
  

Time Complexity:

Best Case: O(1) - Element found at the middle position
Average Case: O(log n) - Logarithmic time complexity
Worst Case: O(log n) - Element not found or at the edge

Space Complexity:

Iterative: O(1) - Constant extra space
Recursive: O(log n) - Call stack space proportional to recursion depth

Advantages of Binary Search:

Very efficient for large datasets - O(log n) is much faster than O(n) for large n
Requires fewer comparisons than linear search

Disadvantages:

Requires sorted data
Sorting may offset the advantage if data is initially unsorted
Not suitable for linked lists (requires random access)

Comparison: Linear vs. Binary Search

Aspect	Linear Search	Binary Search
Time Complexity	O(n)	O(log n)
Data Requirement	Works on sorted or unsorted data	Requires sorted data
Best For	Small datasets, unsorted data	Large datasets, sorted data
Implementation	Simple	More complex
Data Structure	Works with arrays and linked lists	Requires random access (arrays)

Practical Example: Searching in a phonebook

Linear Search: Start with the first page and check each page one by one
Binary Search: Open to the middle, decide whether to go left or right, repeat

For a phonebook with 1000 pages:

Linear search: up to 1000 checks
Binary search: at most 10 checks (log₂ 1000 ≈ 10)

Practice with LeetCode Problems

Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are an excellent alternative for practicing search algorithms.

Linear Search Problems:

Find Numbers with Even Number of Digits - Apply linear search with filtering
Richest Customer Wealth - Linear search with nested arrays
Check If N and Its Double Exist - Search problem that can be solved with linear search

Binary Search Problems:

Binary Search - Basic implementation of binary search
Search Insert Position - Find position to insert into a sorted array
First Bad Version - Application of binary search
Find First and Last Position of Element in Sorted Array - More advanced binary search problem