Searching Algorithms

Searching algorithms find elements in data structures. Linear search works on any structure, binary search requires sorted arrays.

Animated Visualization

Step 1 of 8

Binary Search: Array sorted [10...90], search for 50. Middle = index 4 (50)

javascript

← Scroll →

// 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
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;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;
}
// Recursive Binary Search
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;
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}
// Time Complexity:
// Linear Search: O(n)
// Binary Search: O(log n)
// Space Complexity:
// Linear Search: O(1)
// Binary Search: O(1) iterative, O(log n) recursive

Swipe horizontally to view full code

Explanation

Searching algorithms find elements in data structures. Linear search checks each element sequentially (O(n)). Binary search divides the search space in half each time (O(log n)) but requires a sorted array.

Operations & Complexity

Linear SearchO(n)

Sequential search through array

Binary SearchO(log n)

Divide and conquer on sorted array

Ternary SearchO(log₃ n)

Divide into three parts

Interpolation SearchO(log log n)

Improved binary search for uniform data

Time Complexity