Binary Search from Scratch (2026)
Binary search is one of the most important algorithms in computer science. It finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. With O(log n) time complexity, it is exponentially faster than linear search for large datasets. The key insight is that at each step, we can eliminate half of the remaining elements.
In this tutorial, we will implement the classic binary search, understand lower and upper bound, handle edge cases properly, and explore variations like searching in rotated arrays, finding peak elements, and the ceiling and floor problem. Mastering binary search is essential for efficient algorithm design.
Classic Binary Search
Binary search maintains two pointers, low and high, representing the current search interval. We compute the middle index and compare the middle element with the target. If the middle element equals the target, we return its index. If the target is smaller, we search the left half; if larger, the right half. We repeat until low exceeds high (target not found).
Binary search requires the array to be sorted and supports O(1) random access. The time complexity is O(log n) because the search space is halved at each step. For n = 1 billion, binary search needs at most 30 comparisons compared to 1 billion for linear search.
#include
#include
using namespace std;
int binarySearch(vector& arr, int target) {
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int binarySearchRecursive(vector& arr, int t, int low, int high) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == t) return mid;
else if (arr[mid] < t)
return binarySearchRecursive(arr, t, mid+1, high);
else
return binarySearchRecursive(arr, t, low, mid-1);
} Lower Bound and Upper Bound
Lower bound finds the first position where the target could be inserted to keep the array sorted (first element >= target). Upper bound finds the first position where the target could be inserted to keep all elements less than target (first element > target). Together, they can count occurrences: count = upper_bound - lower_bound.
These operations are fundamental in C++ STL (lower_bound, upper_bound) and Python (bisect_left, bisect_right). They are essential for range queries, finding duplicates, and solving many competitive programming problems efficiently.
import bisect
def lower_bound(arr, target):
return bisect.bisect_left(arr, target)
def upper_bound(arr, target):
return bisect.bisect_right(arr, target)
def lower_bound_manual(arr, target):
low, high = 0, len(arr)
while low < high:
mid = (low + high) // 2
if arr[mid] < target: low = mid + 1
else: high = mid
return low
def upper_bound_manual(arr, target):
low, high = 0, len(arr)
while low < high:
mid = (low + high) // 2
if arr[mid] <= target: low = mid + 1
else: high = mid
return low
arr = [1, 2, 2, 2, 3, 4, 5]
print(lower_bound(arr, 2)) # 1
print(upper_bound(arr, 2)) # 4
print(upper_bound(arr,2) - lower_bound(arr,2)) # 3Binary Search Variations
Binary search has many important variations. Search in a rotated sorted array handles arrays that have been rotated at some pivot. Find the peak element in a mountain array. Find the square root using binary search on the answer space. These variations show that binary search is not just for finding elements but for finding the optimal answer in a monotonic search space.
The key to solving these problems is identifying the monotonic property and defining the correct search condition.
public class BinarySearchVariations {
static int searchRotated(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[low] <= arr[mid]) {
if (arr[low] <= target && target < arr[mid]) high = mid - 1;
else low = mid + 1;
} else {
if (arr[mid] < target && target <= arr[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}
static int findPeak(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) low = mid + 1;
else high = mid;
}
return low;
}
}Binary Search on Answer
Binary search on answer is a powerful technique where we binary search over the range of possible answers. For problems like minimum largest sum after partitioning or maximum minimum distance between elements, we define a predicate function that checks if a given answer is feasible. If feasible, we search lower; otherwise, we search higher.
This technique transforms optimization problems into decision problems. The key requirements are: the answer space must be monotonic (if answer x is feasible, then all values greater than x are also feasible, or vice versa).
def min_capacity(weights, days):
def canShip(capacity):
current_load = 0
days_needed = 1
for w in weights:
if current_load + w > capacity:
days_needed += 1
current_load = w
else:
current_load += w
return days_needed <= days
low, high = max(weights), sum(weights)
while low < high:
mid = (low + high) // 2
if canShip(mid): high = mid
else: low = mid + 1
return low
def min_eating_speed(piles, h):
def canEat(k):
return sum((p + k - 1) // k for p in piles) <= h
low, high = 1, max(piles)
while low < high:
mid = (low + high) // 2
if canEat(mid): high = mid
else: low = mid + 1
return lowFrequently Asked Questions
Why use mid = low + (high - low) / 2?
Using (low + high) / 2 can cause integer overflow when low and high are large. The formula low + (high - low) / 2 computes the same midpoint without overflow.
When does binary search fail?
Binary search fails when the array is not sorted, when there is no random access (linked list), or when the search space is not monotonic. Always verify the preconditions.
What is binary search on answer?
Binary search on answer is used for optimization problems where we binary search over possible answers and check feasibility using a predicate function. The answer space must be monotonic.
How to handle duplicates in binary search?
Classic binary search may return any matching index. Use lower_bound for first occurrence and upper_bound for last occurrence. Count of target = upper_bound - lower_bound.
Originally published on Ayodhyyya. Last updated June 1, 2026.