Log inSign up
easyLeetCodeNot Started

Binary Search

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on LeetCode
Lesson

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.

Example 1 · Target Present in Array:

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

Example 2 · Target Absent from Array:

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

Example 3 · Single Element Found:

Input: nums = [5], target = 5
Output: 0
Explanation: 5 is the only element at index 0.

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the core low <= high loop invariant and mid pointer calculation.
  • Understand why mid = low + (high - low) / 2 prevents integer arithmetic overflow.
  • Contrast iterative O(1) space binary search with recursive O(log N) stack frames.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array is sorted in ascending (or descending) order
  • Requirement for O(log N) search runtime
  • Finding exact value or boundary condition in ordered domain

Algorithmic Decision Tree:

  • Initialize low = 0, high = n - 1.
  • Loop while low <= high.
  • Compute mid = low + (high - low) / 2 to safely prevent integer overflow.
  • If nums[mid] == target, return mid.
  • If nums[mid] < target, eliminate left half by setting low = mid + 1.
  • If nums[mid] > target, eliminate right half by setting high = mid - 1.
  • If loop finishes without returning, return -1.

Connected Patterns:

Search Insert PositionLower BoundUpper BoundSearch in Rotated Sorted Array

1. Linear Search

Intuition

Iterate across the array using a simple for-loop. Check if (nums[i] == target) return i;. If loop finishes without a match, return -1. This ignores the sorted property of the array.

When to apply: Unsorted arrays or very small arrays (N <= 5) where binary search overhead is negligible.

Algorithm

  1. Step 1: Iterate index i from 0 to nums.length - 1.
  2. Step 2: Check if nums[i] equals target.
  3. Step 3: If equal, return index i immediately.
  4. Step 4: If loop completes without finding target, return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int search(vector<int>& nums, int target) {
9 for (int i = 0; i < (int)nums.size(); i++) {
10 if (nums[i] == target) return i;
11 }
12 return -1;
13 }
14};
15
16int main() {
17 Solution sol;
18 vector<int> nums = {-1, 0, 3, 5, 9, 12};
19 cout << "Linear Search result: " << sol.search(nums, 9) << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(N) — In the worst case (target at last index or absent), scans all N elements.
  • Space complexity: O(1) — Only uses a single loop counter index variable.

2. Recursive Binary Search

Intuition

Define helper binarySearch(nums, low, high, target). Base case: if low > high, return -1. Compute mid = low + (high - low) / 2. If nums[mid] == target, return mid. If nums[mid] < target, recurse on (mid + 1, high). Otherwise recurse on (low, mid - 1).

When to apply: Conceptual divide-and-conquer demonstrations or functional programming styles.

Algorithm

  1. Step 1: Check base condition: if low > high, return -1.
  2. Step 2: Calculate mid = low + (high - low) / 2.
  3. Step 3: If nums[mid] == target, return mid.
  4. Step 4: If nums[mid] < target, return recursive call binarySearch(nums, mid + 1, high, target).
  5. Step 5: If nums[mid] > target, return recursive call binarySearch(nums, low, mid - 1, target).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 int binarySearch(const vector<int>& nums, int low, int high, int target) {
8 if (low > high) return -1;
9 int mid = low + (high - low) / 2;
10 if (nums[mid] == target) return mid;
11 if (nums[mid] < target) return binarySearch(nums, mid + 1, high, target);
12 return binarySearch(nums, low, mid - 1, target);
13 }
14
15public:
16 int search(vector<int>& nums, int target) {
17 return binarySearch(nums, 0, nums.size() - 1, target);
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> nums = {-1, 0, 3, 5, 9, 12};
24 cout << "Recursive BS result: " << sol.search(nums, 9) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval at each level, generating a recursion tree of depth log2(N).
  • Space complexity: O(log N) — O(log N) auxiliary space consumed by the call stack frames.

3. Iterative Binary Search (Gold Standard)

Intuition

Maintain low = 0 and high = nums.length - 1. In each iteration of while (low <= high): compute mid = low + (high - low) / 2. If nums[mid] == target, return mid. If nums[mid] < target, shift low = mid + 1. Otherwise shift high = mid - 1. If loop exits, target does not exist; return -1.

When to apply: Industry standard optimal solution for searching sorted collections.

Algorithm

  1. Step 1: Initialize pointer low = 0 and pointer high = nums.length - 1.
  2. Step 2: Enter while loop with condition low <= high.
  3. Step 3: Calculate mid = low + Math.floor((high - low) / 2) to avoid integer overflow.
  4. Step 4: Check if nums[mid] == target; if so, return mid immediately.
  5. Step 5: If nums[mid] < target, eliminate left half by updating low = mid + 1.
  6. Step 6: If nums[mid] > target, eliminate right half by updating high = mid - 1.
  7. Step 7: If loop terminates (low > high), target is absent; return -1.

Binary Search Execution Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Initialize search interval: low = 0, high = 5
Visual state
Values and pointers at this exact step
array
S
-1
0
3
5
9
12
0
↑ low
1
2
↑ mid
3
4
5
↑ high
Variables at this step
low
0
high
5
mid
2
midVal
3
target
9
Check / comparison
nums[mid] = 3 vs target = 9 -> 3 < 9
Decision / next transition
Since 3 < 9, target lies strictly in right half. Set low = mid + 1 = 3.
Why this step matters

Initialize search interval: low = 0, high = 5. Calculate mid = 0 + (5 - 0) / 2 = 2. Value at mid is nums[2] = 3.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int search(vector<int>& nums, int target) {
9 int low = 0;
10 int high = (int)nums.size() - 1;
11
12 while (low <= high) {
13 int mid = low + (high - low) / 2; // Prevents overflow
14
15 if (nums[mid] == target) {
16 return mid;
17 } else if (nums[mid] < target) {
18 low = mid + 1; // Discard left half
19 } else {
20 high = mid - 1; // Discard right half
21 }
22 }
23 return -1;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> nums = {-1, 0, 3, 5, 9, 12};
30 int target = 9;
31 cout << "Optimal Binary Search for " << target << ": index " << sol.search(nums, target) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(log N) — Search space is halved in every iteration: N -> N/2 -> N/4 -> ... -> 1 in log2(N) steps.
  • Space complexity: O(1) — Requires only three integer pointers (low, mid, high) with zero stack or heap allocations.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear SearchO(N)O(1)Scan all elements sequentially from left to right.Linear sequential iteration
2.Recursive Binary SearchO(log N)O(log N)Divide search space recursively with call stack frames.Recursion stack limit
3.Iterative Binary SearchOptimalO(log N)O(1)Halve search space iteratively using two pointers low and high.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Writing while (low < high) instead of while (low <= high) (misses checking single-element search windows when low == high).

Pitfall 2:

Updating low = mid or high = mid instead of mid + 1 or mid - 1 (causes infinite loops).

Pitfall 3:

Integer overflow when computing (low + high) / 2 instead of low + (high - low) / 2.

Crucial Edge Cases to Validate:

  • Single Element Array [5], target = 5 -> low = 0, high = 0, mid = 0 -> returns 0 immediately.
  • Single Element Array [5], target = 2 -> low = 0, high = 0, mid = 0 (5 > 2) -> high = -1 -> returns -1.
  • Target Smaller than Smallest Element: nums = [2, 4, 6], target = 1 -> returns -1.
  • Target Larger than Largest Element: nums = [2, 4, 6], target = 10 -> returns -1.
  • Target at First/Last Index (Boundary elements) -> low or high matches directly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the loop invariant: target is guaranteed to be in nums[low..high] if it exists at all.
  2. Explain why low <= high is required so that 1-element intervals [x, x] are properly examined.
  3. Mention that binary search extends beyond arrays to any monotonic predicate function (Binary Search on Answer).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is mid = low + (high - low) / 2 preferred over mid = (low + high) / 2 in typed languages like C++ and Java?

2.What is the maximum number of comparisons binary search performs on an array of 1,000,000 elements?

Back to DSA Sheet