loading

Binary Search — Step-by-Step Visualization

easyLeetCode #704ArrayBinary Search

Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

Algorithm Pattern

Decrease and Conquer (Binary Search)

Key Idea

Since the array is sorted, we can compare the target with the middle element. If the target is smaller, it must be in the left half. If it's larger, it must be in the right half. This halves the search space at each step, leading to logarithmic time complexity.

Step-by-Step Approach

  1. Initialize `low = 0` and `high = len(nums) - 1`.
  2. While `low <= high`:
  3. `mid = low + (high - low) // 2`.
  4. If `nums[mid] == target`, return `mid`.
  5. Else if `nums[mid] < target`, `low = mid + 1`.
  6. Else `high = mid - 1`.
  7. Return -1 if not found.

Common Gotchas

  • Avoid overflow by using `low + (high - low) // 2` instead of `(low + high) // 2`.
  • Ensure the loop condition is `low <= high` to handle arrays of size 1.

Related Problems

← All problems