Pattern : Binary Search — Problem Statement & Solution Guide
Problem Description
Given a sorted array of integers and a target value, find the index of the target value in the array using binary search. If the target is not found, return -1.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Pattern : Binary Search"
WHY DOES IT MATTER?
The binary search pattern is fundamental because it transforms linear-time problems into logarithmic ones, enabling real‑time responsiveness in systems that must query massive, ordered datasets. Mastery of this pattern signals a candidate's ability to reason about algorithmic efficiency and to leverage data ordering—a skill repeatedly tested in system design and performance‑critical code.
OPTIMIZATION CHALLENGE
The key insight is the invariant that the target, if it exists, must lie within the current low‑high interval. By discarding half of the interval each iteration, the algorithm reduces the problem size exponentially, achieving O(log n) time with only constant extra space.
REAL-WORLD CONNECTION
Think of a library's catalog: instead of walking aisle by aisle (linear scan), you ask the librarian to halve the range of shelves repeatedly until the desired book's location is pinpointed. In distributed systems, this mirrors how consistent hashing or range partitioning narrows down the node responsible for a key.
During an interview, write the loop with clear low, high, and mid calculations, and guard against overflow by using mid = low + (high - low) / 2. Also, explicitly handle edge cases like empty arrays and single‑element arrays to demonstrate thoroughness.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
Binary search is a divide‑and‑conquer algorithm that exploits the monotonic ordering of a sorted array. By repeatedly halving the search interval, it discards half of the remaining elements at each step, guaranteeing logarithmic time performance. The algorithm maintains two pointers, low and high, representing the current search bounds, computes the middle index, and compares the middle element with the target to decide which half to explore next. This systematic reduction continues until the target is found or the interval becomes empty.
A naive linear scan examines each element sequentially, resulting in O(n) time. While acceptable for tiny inputs, it becomes prohibitive for large datasets—think millions of records—because the runtime grows linearly with size. Binary search, by contrast, runs in O(log n) time, making it scalable for massive, sorted collections such as database indexes, file system directories, or in‑memory caches. The optimal paradigm here is the logarithmic search pattern, which is the cornerstone of many higher‑level data structures like balanced trees and skip lists.
The correctness of binary search hinges on the invariant that the target, if present, always resides within the current low‑high window. Maintaining this invariant while updating pointers ensures termination after at most ⌊log₂ n⌋+1 iterations. Space usage stays constant because the algorithm only needs a few integer variables, achieving O(1) auxiliary space.
Interview Questions on This Problem
Q1How would you modify binary search to find the first occurrence of a duplicate target in a sorted array?
After locating any instance of the target, continue searching the left half by setting high = mid - 1 while still checking for equality. Keep track of the best index found; when the loop ends, the stored index is the first occurrence.
Q2Explain how binary search can be applied to search in an infinite sorted stream where the size is unknown.
First exponentially expand the search window (e.g., 1, 2, 4, 8…) until the target is less than or equal to the element at the high index, establishing an upper bound. Then perform standard binary search within the identified low‑high range.
Q3Why is binary search unsuitable for searching in an unsorted array, and what preprocessing step can make it viable?
Binary search relies on the total order property; without sorting, the mid‑element comparison provides no guarantee about the target's location, leading to incorrect results. Sorting the array first (O(n log n)) creates the required order, after which binary search can be applied.
Examples
Input
[1, 2, 3, 4, 5], target = 3
Output
2
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and target = 3, we perform binary search. We start by finding the middle element (3). Since the target is equal to the middle element, we return the index of the middle element, which is 2.
Input
[1, 2, 3, 4, 5], target = 6
Output
-1
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and target = 6, we perform binary search. We start by finding the middle element (3). Since the target is greater than the middle element, we repeat the process with the right half of the array. However, the target is not found in the array, so we return -1 to indicate that the target is not present.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Maintain low and high pointers, compute the middle index, compare the middle element with the target, and adjust the pointers to narrow the search space by half each iteration.
Brute Force Approach
Iterate through the array from start to finish, comparing each element with the target until a match is found or the array ends.
Verified Code Solutions
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}class Solution {
public:
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}class Solution {
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.