Fundamentals
Fundamentals is a easy binary search problem solved with the basics pattern.
The best approach, binary search templates, runs in O(log n) time and O(1) space.
Below are 2 approaches in Java, from linear scan (baseline) up.
Problem
Binary search finds a target, or a boundary, in a sorted or monotonic search space by halving the range every step. Before solving the problems in this topic, learn the two loop templates and how to avoid the two classic bugs: overflow in the midpoint and loops that never shrink.
Examples
Example 1
- Input
Search space [lo, hi] = [0, 7] in a sorted array of 8- Output
At most 4 comparisons- Why
- Each step halves the range: 8 → 4 → 2 → 1.
Example 2
- Input
lo = 2^31 - 10, hi = 2^31 - 2- Output
mid = lo + (hi - lo) / 2- Why
- (lo + hi) / 2 would overflow an int.
Constraints
- Works on anything that is sorted or monotonic: if a condition is true at x, it stays true for every larger x (or smaller).
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Linear scan (baseline) | O(n) | O(1) |
| Binary search templates | O(log n) | O(1) |
1Linear scan (baseline)
O(n)O(1)Check every element. It is always correct and ignores the sorted order, so it is the baseline binary search improves on.
- for i in 0..n-1: if a[i] == target return i.
class Solution {
static int linear(int[] a, int target) {
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;
return -1;
}
}2Binary search templates
O(log n)The range halves each iteration.O(1)Closed interval [lo, hi]: loop while lo <= hi, and move lo = mid + 1 or hi = mid - 1. Half-open [lo, hi): loop while lo < hi, move lo = mid + 1 or hi = mid. The half-open version with a boolean check ok(mid) finds the first index where the condition becomes true, and it is the template behind bisect, first/last position and search on the answer.
- Pick an interval convention and write down the loop invariant.
- mid = lo + (hi - lo) / 2 to avoid overflow.
- Every branch must shrink the range, or the loop never ends.
class Solution {
// closed interval: exact match
static int search(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// half-open interval: first index where a[i] >= target
static int firstAtLeast(int[] a, int target) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= target) hi = mid;
else lo = mid + 1;
}
return lo;
}
}Edge cases to test
- Empty search space
- Target smaller than every element, or larger
- Two elements left (the classic infinite-loop case)
Hints
Hint 1
Decide first: is hi inclusive or exclusive? Then keep every update consistent with that choice.
FAQ
What is the best time complexity for Fundamentals?
Binary search templates runs in O(log n) time and O(1) extra space. The range halves each iteration.
Which pattern does Fundamentals use?
It is a binary search problem that uses the basics pattern. Other problems with the same pattern: Binary Search.
Is there a brute force solution for Fundamentals?
Yes. Linear scan (baseline) takes O(n) time and O(1) space. Check every element.
Which edge cases should I test for Fundamentals?
Empty search space; Target smaller than every element, or larger; Two elements left (the classic infinite-loop case).