Binary Search

Easyarraybinary-search
Category: Binary Search
Companies that ask this question:
AmazonMicrosoftGoogleFacebook

Approach

Binary Search

Problem Statement

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.

Examples

Example 1:

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

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Approach

Binary Search Algorithm

The classic binary search algorithm is the optimal solution for searching in a sorted array.

Key Insight:

  • Since the array is sorted, we can eliminate half of the remaining elements in each iteration
  • Compare the target with the middle element
  • If target is smaller, search left half; if larger, search right half
  • Continue until target is found or search space is exhausted

Algorithm:

  1. Initialize two pointers: left = 0 and right = len(nums) - 1
  2. While left <= right:
    • Calculate middle index: mid = left + (right - left) / 2
    • If nums[mid] == target, return mid
    • If nums[mid] < target, search right half: left = mid + 1
    • If nums[mid] > target, search left half: right = mid - 1
  3. If target not found, return -1

Why left + (right - left) / 2 instead of (left + right) / 2?

  • Prevents integer overflow in languages like Java/C++
  • In Python, both are safe, but the former is a good practice

Complexity Analysis

  • Time Complexity: O(log n)

    • Each iteration eliminates half of the remaining elements
    • Maximum iterations = log₂(n)

  • Space Complexity: O(1)

    • Only uses a constant amount of extra space
    • Iterative solution doesn't use recursion stack

Edge Cases

  1. Empty array: Return -1
  2. Single element: Check if it equals target
  3. Target smaller than all elements: Return -1
  4. Target larger than all elements: Return -1
  5. Duplicate elements: Return any valid index (problem states sorted array)

Common Mistakes

  1. Off-by-one errors: Using left < right instead of left <= right
  2. Integer overflow: Using (left + right) / 2 in languages with fixed integer sizes
  3. Incorrect mid calculation: Forgetting to update left or right correctly
  4. Infinite loop: Not updating pointers properly (e.g., left = mid instead of left = mid + 1)

Visual Intuition

Initial: [-1, 0, 3, 5, 9, 12], target = 9
          L        M        R

Step 1: nums[mid] = 3 < 9, search right
        [-1, 0, 3, 5, 9, 12]
                    L  M  R

Step 2: nums[mid] = 9 == 9, found!
        [-1, 0, 3, 5, 9, 12]
                       ↑
                    index 4

Related Problems

  • Search Insert Position
  • First Bad Version
  • Search in Rotated Sorted Array
  • Find Minimum in Rotated Sorted Array

Solution

java
1/**
2 * Binary Search
3 * Time: O(log n)
4 * Space: O(1) iterative, O(log n) recursive
5 */
6
7// Approach 1: Iterative Binary Search (Optimal)
8class Solution {
9    public int search(int[] nums, int target) {
10        int left = 0, right = nums.length - 1;
11        
12        while (left <= right) {
13            // Avoid overflow: left + (right - left) / 2
14            int mid = left + (right - left) / 2;
15            
16            if (nums[mid] == target) {
17                return mid;
18            } else if (nums[mid] < target) {
19                left = mid + 1;  // Search right half
20            } else {
21                right = mid - 1;  // Search left half
22            }
23        }
24        
25        return -1;  // Target not found
26    }
27}
28
29// Approach 2: Recursive Binary Search
30class Solution2 {
31    public int search(int[] nums, int target) {
32        return binarySearch(nums, target, 0, nums.length - 1);
33    }
34    
35    private int binarySearch(int[] nums, int target, int left, int right) {
36        if (left > right) {
37            return -1;
38        }
39        
40        int mid = left + (right - left) / 2;
41        
42        if (nums[mid] == target) {
43            return mid;
44        } else if (nums[mid] < target) {
45            return binarySearch(nums, target, mid + 1, right);
46        } else {
47            return binarySearch(nums, target, left, mid - 1);
48        }
49    }
50}
51
Loading visualizer...