Searching

Binary Search

What is Binary Search?

Binary Search only works because the list is already sorted, and it takes full advantage of that: check the middle element, and if the target is smaller, throw away the entire upper half; if it's larger, throw away the entire lower half. Repeating that halving keeps shrinking the search space until you land on the value.

How Does It Work?

Imagine you have a sorted list of numbers: [1, 3, 5, 7, 9, 11, 13] and you want to find the number 7.

  1. Compare 7 with the middle element (7). It matches! Return the position.
    low103152mid7394115high136
  2. If searching for 5:
    • First middle is 7 (too high)
      low103152mid7394115high136
    • Search left half: [1, 3, 5]
      low1031high527394115136
    • New middle is 3 (too low)
      low10mid31high527394115136
    • Search right portion: [5]
      1031low527394115136
    • Found at position 2
      1031mid527394115136
Middle elementActive search rangeEliminatedMatch found

If the number is not in the list (e.g., searching for 8), the search ends when the subarray becomes empty.

Algorithm Steps

  1. Start with the entire sorted array
  2. Compare the target with the middle element:
    • If equal, return the position
    • If target is smaller, search the left half
    • If target is larger, search the right half
  3. Repeat until the element is found or the subarray is empty
  4. If not found, return "Not Found"

Time Complexity

  • Best Case: Target is the middle element → O(1).
  • Worst Case: Element not present → O(log n) (halves search space each step).

Time Complexity Analysis

Advertisement

Binary Search is extremely fast for large datasets but requires the list to be sorted beforehand. It's much more efficient than Linear Search for sorted data.

Daily DSA Challenge by Scale Engineer

Visualize how Binary Search efficiently finds an element in a sorted array.

Test Your Knowledge before moving forward!

Binary Search Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Binary Search Implementation

// Binary Search in JavaScript (Iterative)
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; // Target found
    } else if (arr[mid] < target) {
      left = mid + 1; // Search right half
    } else {
      right = mid - 1; // Search left half
    }
  }
  
  return -1; // Target not found
}

// Usage example
const sortedNumbers = [10, 20, 30, 40, 50, 60, 70];
const target = 40;
const result = binarySearch(sortedNumbers, target);

if (result !== -1) {
  console.log(`Element found at index: ${result}`);
} else {
  console.log("Element not found");
}

Done With the Learning

Mark binary search as done and view it on your dashboard

Explore other operations

Linear Search