Binary Search
What is Binary Search
Binary search finds a target value in sorted data by repeatedly checking the middle element and eliminating half of the remaining range based on whether the target is smaller or larger — this only works because the data is sorted, which lets you rule out an entire half without checking it.
Example: What is Binary Search
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int target = 7, low = 0, high = 5;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) { cout << "Found at index " << mid; break; }
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int target = 7, low = 0, high = 5;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) { System.out.println("Found at index " + mid); break; }
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
}
}arr = [1, 3, 5, 7, 9, 11]
target = 7
low, high = 0, 5
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
print("Found at index", mid)
break
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1#include <stdio.h>
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int target = 7, low = 0, high = 5;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) { printf("Found at index %d", mid); break; }
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return 0;
}Login to try C/C++/Java code in the editor
How It Works
At each step, compare the target to the value at the midpoint of the current range: if they match, you're done; if the target is smaller, discard the right half and search the left half; if larger, discard the left half and search the right half.
Example: How It Works
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int target = 3, low = 0, high = 5;
while (low <= high) {
int mid = (low + high) / 2;
cout << "mid=" << mid << " value=" << arr[mid] << endl;
if (arr[mid] == target) break;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int target = 3, low = 0, high = 5;
while (low <= high) {
int mid = (low + high) / 2;
System.out.println("mid=" + mid + " value=" + arr[mid]);
if (arr[mid] == target) break;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
}
}arr = [1, 3, 5, 7, 9, 11]
target = 3
low, high = 0, 5
while low <= high:
mid = (low + high) // 2
print("mid=", mid, "value=", arr[mid])
if arr[mid] == target:
break
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1#include <stdio.h>
int main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int target = 3, low = 0, high = 5;
while (low <= high) {
int mid = (low + high) / 2;
printf("mid=%d value=%d\n", mid, arr[mid]);
if (arr[mid] == target) break;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return 0;
}Login to try C/C++/Java code in the editor
Search Boundaries
Two pointers, typically called low and high, mark the current search range's boundaries; the midpoint is calculated between them each step, and after eliminating half the range, one of the two boundaries moves to shrink the range for the next comparison.
Example: Search Boundaries
#include <iostream>
using namespace std;
int main() {
int low = 0, high = 5;
int mid = (low + high) / 2;
cout << "low=" << low << " high=" << high << " mid=" << mid;
return 0;
}public class Main {
public static void main(String[] args) {
int low = 0, high = 5;
int mid = (low + high) / 2;
System.out.println("low=" + low + " high=" + high + " mid=" + mid);
}
}low, high = 0, 5
mid = (low + high) // 2
print("low=", low, "high=", high, "mid=", mid)#include <stdio.h>
int main() {
int low = 0, high = 5;
int mid = (low + high) / 2;
printf("low=%d high=%d mid=%d", low, high, mid);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
Binary search takes O(log n) time because each comparison halves the remaining search space, and O(1) extra space when done iteratively with just the two boundary pointers — a dramatic improvement over linear search's O(n) on large sorted datasets.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Binary search: O(log n) time, O(1) extra space when done iteratively";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Binary search: O(log n) time, O(1) extra space when done iteratively");
}
}print("Binary search: O(log n) time, O(1) extra space when done iteratively")#include <stdio.h>
int main() {
printf("Binary search: O(log n) time, O(1) extra space when done iteratively");
return 0;
}Login to try C/C++/Java code in the editor
Common Variation
When the sorted data contains duplicate values, a standard binary search may land on any one of the matching elements — a common variation adjusts the comparison logic to specifically find the first (or last) occurrence of the target instead of just any match.
Example: Common Variation
#include <iostream>
using namespace std;
int main() {
cout << "With duplicates, a standard binary search may land on any matching index, not necessarily the first or last";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last");
}
}print("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last")#include <stdio.h>
int main() {
printf("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: