Searching Algorithms

Searching Algorithms

Searching finds the position of a target value in a data structure.

Linear Search - O(n)

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

Binary Search - O(log n)

Requires sorted array. Repeatedly divides search space in half.

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;
  }

  

    
Learn More
    

      
        
GeeksforGeeks: Searching
        
Learn about Linear Search, Binary Search, and more.
      
      
        
LeetCode: Binary Search
        
Solve binary search problems to master the technique.
      
    
  

  
  return -1;
}

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

Binary Search Variants

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