Binary Search

Difficulty: Easy

Problem

Given a sorted array of integers nums and a target value, return the index of the target if it is found. If not, return -1. You must write an algorithm with O(log n) runtime complexity.

Example

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in nums at index 4.

Brute-force approach

Scan every element from left to right until the target is found or the array is exhausted.

Steps

  1. For each index i from 0 to n-1:
  2. If nums[i] == target, return i
  3. If loop ends without finding target, return -1

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Checks every element — doesn't use the sorted property at all
  • O(n) is too slow for large arrays when O(log n) is possible
  • For 1 billion elements, linear scan needs up to 1 billion checks vs ~30 for binary search

Optimal approach

Key insight: In a sorted array, one comparison with the middle element tells you which half the target must be in — instantly eliminating 50% of remaining elements. A subtle but critical detail: use mid = left + (right - left) / 2 instead of mid = (left + right) / 2 to avoid integer overflow.

Repeatedly compare the middle element with the target. If middle < target, search the right half. If middle > target, search the left half. Each step eliminates half the array.

Steps

  1. Set left = 0, right = n - 1
  2. While left <= right:
  3. mid = left + (right - left) / 2
  4. If nums[mid] == target: return mid
  5. If nums[mid] < target: left = mid + 1
  6. If nums[mid] > target: right = mid - 1
  7. Return -1 (not found)

Time complexity: O(log n) · Space complexity: O(1)