Binary Search Algorithm - Complete Guide

Binary search is one of the most fundamental algorithms in computer science. It efficiently finds elements in sorted arrays with O(log n) time complexity.

What is Binary Search? #

Binary search is a divide-and-conquer algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.

How Binary Search Works #

Start with the middle element
If target equals middle, return the index
If target is less than middle, search the left half
If target is greater than middle, search the right half
Repeat until target is found or interval is empty

Visual Example #

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

Step 1: Check middle (9)
[1, 3, 5, 7, 9, | 11, 13, 15, 17, 19]
13 > 9, search right half

Step 2: Check middle of right half (15)
[11, 13, 15, 17, 19]
      ^
13 < 15, search left half

Step 3: Check middle of left half (13)
[11, 13]
     ^
Found! Return index 6

Basic Implementation #

Iterative Approach #

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;  // Found
    } else if (arr[mid] < target) {
      left = mid + 1;  // Search right half
    } else {
      right = mid - 1;  // Search left half
    }
  }

  return -1;  // Not found
}

const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(arr, 7));  // 3
console.log(binarySearch(arr, 99));  // -1

Recursive Approach #

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1;  // Not found
  }

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

const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearchRecursive(arr, 9));  // 4

Avoiding Integer Overflow #

In some languages, (left + right) / 2 can cause overflow. Use this instead:

// Better
const mid = left + Math.floor((right - left) / 2);

// Or using bit shift
const mid = (left + right) >>> 1;

Binary Search Variants #

Find First Occurrence #

function findFirst(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let 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;
}

const arr = [1, 2, 2, 2, 3, 4, 5];
console.log(findFirst(arr, 2));  // 1

Find Last Occurrence #

function findLast(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      result = mid;
      left = mid + 1;  // Continue searching right
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

const arr = [1, 2, 2, 2, 3, 4, 5];
console.log(findLast(arr, 2));  // 3

Find Insert Position #

function searchInsert(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 left;  // Insert position
}

const arr = [1, 3, 5, 6];
console.log(searchInsert(arr, 5));  // 2
console.log(searchInsert(arr, 2));  // 1
console.log(searchInsert(arr, 7));  // 4

Find Peak Element #

function findPeakElement(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] > arr[mid + 1]) {
      right = mid;  // Peak in left half or mid
    } else {
      left = mid + 1;  // Peak in right half
    }
  }

  return left;
}

const arr = [1, 2, 3, 1];
console.log(findPeakElement(arr));  // 2 (value 3)

Advanced Binary Search Problems #

Search in Rotated Sorted Array #

function searchRotated(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;
    }

    // Determine which half is sorted
    if (arr[left] <= arr[mid]) {
      // Left half is sorted
      if (arr[left] <= target && target < arr[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (arr[mid] < target && target <= arr[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

const arr = [4, 5, 6, 7, 0, 1, 2];
console.log(searchRotated(arr, 0));  // 4
console.log(searchRotated(arr, 3));  // -1

Find Minimum in Rotated Sorted Array #

function findMin(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] > arr[right]) {
      // Minimum is in right half
      left = mid + 1;
    } else {
      // Minimum is in left half or mid
      right = mid;
    }
  }

  return arr[left];
}

const arr = [4, 5, 6, 7, 0, 1, 2];
console.log(findMin(arr));  // 0

Search 2D Matrix #

function searchMatrix(matrix, target) {
  if (!matrix.length || !matrix[0].length) 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 row = Math.floor(mid / cols);
    const col = mid % cols;
    const value = matrix[row][col];

    if (value === target) {
      return true;
    } else if (value < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}

const matrix = [
  [1,  3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
];
console.log(searchMatrix(matrix, 3));  // true
console.log(searchMatrix(matrix, 13));  // false

Find Square Root #

function mySqrt(x) {
  if (x < 2) return x;

  let left = 1;
  let right = Math.floor(x / 2);

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const square = mid * mid;

    if (square === x) {
      return mid;
    } else if (square < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return right;  // Floor of square root
}

console.log(mySqrt(4));  // 2
console.log(mySqrt(8));  // 2
console.log(mySqrt(16));  // 4

Koko Eating Bananas #

function minEatingSpeed(piles, h) {
  let left = 1;
  let right = Math.max(...piles);

  function canFinish(speed) {
    let hours = 0;
    for (const pile of piles) {
      hours += Math.ceil(pile / speed);
    }
    return hours <= h;
  }

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (canFinish(mid)) {
      right = mid;  // Try slower
    } else {
      left = mid + 1;  // Must be faster
    }
  }

  return left;
}

console.log(minEatingSpeed([3, 6, 7, 11], 8));  // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5));  // 30

Capacity to Ship Packages #

function shipWithinDays(weights, days) {
  let left = Math.max(...weights);
  let right = weights.reduce((sum, w) => sum + w, 0);

  function canShip(capacity) {
    let daysNeeded = 1;
    let currentLoad = 0;

    for (const weight of weights) {
      if (currentLoad + weight > capacity) {
        daysNeeded++;
        currentLoad = 0;
      }
      currentLoad += weight;
    }

    return daysNeeded <= days;
  }

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (canShip(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  return left;
}

console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5));  // 15

Binary Search Template #

Standard Template #

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Left Bound Template #

function leftBound(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

Right Bound Template #

function rightBound(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left - 1;
}

Time and Space Complexity #

Aspect	Complexity
Time (Average)	O(log n)
Time (Worst)	O(log n)
Space (Iterative)	O(1)
Space (Recursive)	O(log n)

Binary Search vs Linear Search #

Array Size	Linear Search	Binary Search
10	10 operations	4 operations
100	100 operations	7 operations
1,000	1,000 operations	10 operations
1,000,000	1,000,000 operations	20 operations

When to Use Binary Search #

Use binary search when:

Data is sorted
Need O(log n) time complexity
Random access is available (arrays)
Data set is large

Don’t use binary search when:

Data is unsorted (sorting cost O(n log n))
Data structure is linked list
Data set is very small (linear is simpler)

Common Mistakes #

Wrong loop condition - Use left <= right or left < right correctly
Integer overflow - Use left + (right - left) / 2
Off-by-one errors - Careful with mid + 1 and mid - 1
Unsorted array - Binary search only works on sorted data
Infinite loops - Ensure left/right pointers always progress

Tips for Binary Search Problems #

Identify the search space - What are we searching over?
Define the condition - What makes an answer valid?
Choose the template - Standard, left bound, or right bound?
Handle edge cases - Empty array, single element, not found
Test with examples - Walk through small cases

Binary search is essential for technical interviews and real-world applications. Master the template and common variations to solve problems efficiently.