📚 Binary Search Master Notes (Teacher
Style Hinglish)
These notes cover everything we've studied so far, organized topic-by-topic. Think of this as your
revision handbook before interviews, OA rounds, or contests.
🗺️ Binary Search Roadmap
Phase 1: Binary Search Fundamentals
1. Basic Binary Search
2. Lower Bound / Upper Bound
3. First Occurrence & Last Occurrence
Phase 2: Binary Search Variations
4. Search in Rotated Sorted Array
5. Find Minimum in Rotated Sorted Array
6. Binary Search on Answer
Koko Eating Bananas
Capacity to Ship Packages
Book Allocation
Split Array Largest Sum
7. Aggressive Cows
Phase 3: Binary Search on Matrix
8. Search in 2D Matrix
PHASE 1
Topic 1: Basic Binary Search
Problem
Given sorted array:
[1,3,5,7,9]
Find target:
Core Idea
At every step:
Target < mid → Left
Target > mid → Right
Target == mid → Found
Complexity
O(logn)O(\log n)O(logn)
O(logn)O(\log n)O(logn)
Template
int binarySearch(vector<int>& nums, int target){
int low = 0;
int high = [Link]()-1;
while(low <= high){
int mid = low + (high-low)/2;
if(nums[mid] == target)
return mid;
else if(nums[mid] < target)
low = mid+1;
else
high = mid-1;
}
return -1;
}
Topic 2: Lower Bound
Definition
First position where:
arr[i] >= target
Example
arr = [1,2,4,4,4,7]
target = 4
Answer:
Pattern
F F T T T T
Need:
FIRST TRUE
Code
int lowerBound(vector<int>& arr,int target){
int low=0;
int high=[Link]()-1;
int ans=[Link]();
while(low<=high){
int mid=low+(high-low)/2;
if(arr[mid] >= target){
ans=mid;
high=mid-1;
}
else{
low=mid+1;
}
}
return ans;
}
Topic 3: First and Last Occurrence
First Occurrence
When target found:
Move LEFT
Code
int firstOccurrence(vector<int>& arr,int target){
int low=0;
int high=[Link]()-1;
int ans=-1;
while(low<=high){
int mid=low+(high-low)/2;
if(arr[mid]==target){
ans=mid;
high=mid-1;
}
else if(arr[mid]<target){
low=mid+1;
}
else{
high=mid-1;
}
}
return ans;
}
Last Occurrence
When target found:
Move RIGHT
Code
int lastOccurrence(vector<int>& arr,int target){
int low=0;
int high=[Link]()-1;
int ans=-1;
while(low<=high){
int mid=low+(high-low)/2;
if(arr[mid]==target){
ans=mid;
low=mid+1;
}
else if(arr[mid]<target){
low=mid+1;
}
else{
high=mid-1;
}
}
return ans;
}
PHASE 2
Topic 4: Search in Rotated Sorted Array
LeetCode 33
Example:
[4,5,6,7,0,1,2]
Target:
Golden Observation
At least one half is always sorted.
Decision Tree
Is left sorted?
YES:
Target inside left?
YES → Left
NO → Right
NO:
Right sorted
Target inside right?
YES → Right
NO → Left
Code
int search(vector<int>& nums,int target){
int low=0;
int high=[Link]()-1;
while(low<=high){
int mid=low+(high-low)/2;
if(nums[mid]==target)
return mid;
if(nums[low] <= nums[mid]){
if(target>=nums[low] &&
target<nums[mid])
high=mid-1;
else
low=mid+1;
}
else{
if(target>nums[mid] &&
target<=nums[high])
low=mid+1;
else
high=mid-1;
}
}
return -1;
}
Topic 5: Find Minimum in Rotated Array
LeetCode 153
Example:
[4,5,6,7,0,1,2]
Answer:
Key Observation
Check:
nums[mid] > nums[high]
If true:
Minimum Right
Else:
Minimum Left including mid
Code
int findMin(vector<int>& nums){
int low=0;
int high=[Link]()-1;
while(low<high){
int mid=low+(high-low)/2;
if(nums[mid] > nums[high]){
low=mid+1;
}
else{
high=mid;
}
}
return nums[low];
}
Topic 6: Binary Search on Answer
This is the MOST IMPORTANT topic.
Recognition Signals
If question contains:
minimum possible
maximum possible
maximize minimum
minimize maximum
Think:
Binary Search on Answer
Universal Template
while(low<=high){
int mid=low+(high-low)/2;
if(possible(mid)){
ans=mid;
high=mid-1;
}
else{
low=mid+1;
}
}
Koko Eating Bananas
LeetCode 875
Search Space
1 → max pile
Predicate
hours += ceil(pile/speed)
Efficient form:
⌈ab⌉=a+b−1b\left\lceil \frac{a}{b}\right\rceil = \frac{a+b-1}{b}⌈ba⌉=ba+b−1
⌈ab⌉=a+b−1b\left\lceil \frac{a}{b}\right\rceil=\frac{a+b-1}{b}⌈ba⌉=ba+b−1
Capacity To Ship Packages
LeetCode 1011
Search Space
max weight → total sum
Predicate
Greedy loading.
if(load+weight > capacity)
{
days++;
load=weight;
}
Book Allocation
Same as shipping.
Replace:
Packages → Books
Days → Students
Split Array Largest Sum
LeetCode 410
Exactly Book Allocation.
Replace:
Books → Numbers
Students → Subarrays
Topic 7: Aggressive Cows
Search Space
1
to
last stall - first stall
Predicate
Can we place all cows with distance = mid?
Pattern
TTTTFFFF
Need:
LAST TRUE
Code
bool possible(vector<int>& stalls,
int cows,
int dist){
int count=1;
int last=stalls[0];
for(int i=1;i<[Link]();i++){
if(stalls[i]-last >= dist){
count++;
last=stalls[i];
}
}
return count>=cows;
}
PHASE 3
Topic 8: Search in 2D Matrix
LeetCode 74
Matrix:
1 3 5 7
10 11 16 20
23 30 34 60
Key Observation
Matrix behaves like:
[1,3,5,7,10,11,16,20,23,30,34,60]
A sorted array.
Mapping Formula
For flattened index:
mid
Row:
row=midcolsrow=\frac{mid}{cols}row=colsmid
row=midcolsrow=\frac{mid}{cols}row=colsmid
Column:
col=mid mod colscol=mid \bmod colscol=midmodcols
col=mid mod colscol=mid\bmod colscol=midmodcols
Code
bool searchMatrix(vector<vector<int>>& matrix,
int target){
int rows=[Link]();
int cols=matrix[0].size();
int low=0;
int high=rows*cols-1;
while(low<=high){
int mid=low+(high-low)/2;
int row=mid/cols;
int col=mid%cols;
int value=matrix[row][col];
if(value==target)
return true;
else if(value<target)
low=mid+1;
else
high=mid-1;
}
return false;
}
🎯 Ultimate Binary Search Recognition Sheet
Problem Type Pattern
Search target Normal BS
First occurrence First True
Last occurrence Last True
Lower Bound First ≥ Target
Upper Bound First > Target
Rotated Search One half sorted
Rotated Minimum Detect break point
Koko BS on Answer
Shipping BS + Greedy
Book Allocation BS + Greedy
Split Array BS + Greedy
Aggressive Cows Last True
Matrix Search Flatten Matrix
🧠 Golden Binary Search Rules
Rule 1
Whenever you see:
sorted
Think Binary Search.
Rule 2
Whenever you see:
minimum possible
maximum possible
Think Binary Search on Answer.
Rule 3
Whenever you see:
FFFFTTTT
Find:
FIRST TRUE
Rule 4
Whenever you see:
TTTTFFFF
Find:
LAST TRUE
Rule 5
The hardest part of BS-on-Answer is NOT binary search.
It is writing:
bool possible(...)
If you can design the predicate correctly, the binary search itself becomes almost mechanical.
At this point you've covered roughly 75-80% of the binary search patterns asked in interviews
and coding rounds. The remaining advanced topics are:
Row-wise & Column-wise Sorted Matrix
Median of Row-wise Sorted Matrix
Peak Element (1D & 2D)
Advanced Boundary Binary Search
Binary Search on Real Numbers (decimal answers)
🏔 Topic 1: Row-wise & Column-wise Sorted
Matrix
Problem
Matrix:
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
Find:
14
Observation
Rows sorted:
1 4 7 11
✅
Columns sorted:
1
2
3
10
✅
Naive Approach
for every row
for every col
Complexity:
O(nm)O(nm)O(nm)
O(nm)O(nm)O(nm)
Teacher Trick 🧠
Start from:
Top Right Corner
Why?
Because from there:
Current > Target
Move LEFT.
Current < Target
Move DOWN.
Example
Target = 14
Start:
11
11 < 14
12
12 < 14
16
16 > 14
9
9 < 14
14
Found 🎉
Code
bool searchMatrix(vector<vector<int>>& matrix,
int target){
int row = 0;
int col = matrix[0].size()-1;
while(row < [Link]() && col >= 0){
if(matrix[row][col] == target)
return true;
else if(matrix[row][col] > target)
col--;
else
row++;
}
return false;
}
Recognition Trick 🚨
If matrix says:
Rows sorted
Columns sorted
Think:
Staircase Search
NOT binary search.
LeetCode
LeetCode 240
Search a 2D Matrix II
🏔 Topic 2: Median of Row-wise Sorted
Matrix
This is one of the hardest Binary Search questions.
Problem
1 3 5
2 6 9
3 6 9
Find median.
Brute Force
Flatten:
1 2 3 3 5 6 6 9 9
Median:
Works.
But:
O(nm log(nm))
Too much.
Key Observation
Median means:
Half numbers smaller.
Half numbers bigger.
Suppose:
mid = 5
Count numbers ≤ 5.
If count large enough:
Median left side.
Otherwise:
Median right side.
Binary Search On Answer
Search space:
min element
to
max element
Example:
1 → 9
Predicate
Count:
How many elements <= mid ?
Fast Counting
Each row sorted.
Use:
upper_bound([Link](),
[Link](),
mid)
Complexity:
O(rlogclogrange)O(r \log c \log range)O(rlogclogrange)
O(rlogclog(range))O(r\log c\log(range))O(rlogclog(range))
Recognition Trick 🚨
If problem says:
Median
Rows Sorted
Think:
Binary Search on Value
Not index.
🏔 Topic 3: Peak Element (1D)
LeetCode 162
Array:
1 2 3 1
Peak:
Definition
Peak means:
arr[i] > arr[i-1]
and
arr[i] > arr[i+1]
Genius Observation
If:
arr[mid] < arr[mid+1]
Then peak must exist RIGHT.
Why?
Because array rising.
If:
arr[mid] > arr[mid+1]
Peak exists LEFT including mid.
Code
int findPeakElement(vector<int>& nums){
int low = 0;
int high = [Link]()-1;
while(low < high){
int mid =
low + (high-low)/2;
if(nums[mid] < nums[mid+1])
low = mid+1;
else
high = mid;
}
return low;
}
Visualization
1 2 3 4 5
Always move right.
Peak:
5
5 4 3 2 1
Always move left.
Peak:
Recognition
If question says:
Peak
Mountain
Local Maximum
Think:
Slope Binary Search
🏔 Topic 4: Peak Element (2D)
LeetCode 1901
Very famous.
Example:
10 20 15
21 30 14
7 16 32
Peak:
30
or
32
Brute Force
Check every cell.
Smart Idea
Binary search columns.
Suppose middle column:
20
30
16
Largest:
30
Now compare:
left
right
neighbors.
If right bigger:
Move Right
If left bigger:
Move Left
Otherwise:
Found Peak
Complexity:
O(nlogm)O(n\log m)O(nlogm)
O(nlogm)O(n\log m)O(nlogm)
Recognition
If question says:
2D Peak
Think:
Binary Search Columns
🏔 Topic 5: Advanced Boundary Binary
Search
This is THE MOST IMPORTANT INTERVIEW CONCEPT.
Most candidates know:
Binary Search
Few know:
Boundary Binary Search
Pattern 1
FFFFFTTTTT
Need:
First True
Examples:
Lower Bound
Koko
Shipping
Book Allocation
Split Array
Template
while(low<=high){
int mid = ...
if(valid(mid)){
ans = mid;
high = mid-1;
}
else{
low = mid+1;
}
}
Pattern 2
TTTTTFFFF
Need:
Last True
Examples:
Aggressive Cows
Magnetic Force
Template
if(valid(mid)){
ans = mid;
low = mid+1;
}
else{
high = mid-1;
}
Ultimate Recognition
Interviewer says:
Minimum Possible
Think:
First True
Interviewer says:
Maximum Possible
Think:
Last True
🏔 Topic 6: Binary Search on Real Numbers
Most students never learn this.
But top companies ask it.
Example
Find:
10\sqrt{10}10
10\sqrt{10}10
We know:
3² = 9
4² = 16
Answer between:
3 and 4
Instead of integer BS:
Use decimal BS.
Search Space
3.0 → 4.0
Predicate
mid * mid <= 10
Loop
while(high-low > 1e-6)
Code:
double low = 0;
double high = 10;
while(high-low > 1e-6){
double mid =
low + (high-low)/2;
if(mid*mid <= 10)
low = mid;
else
high = mid;
}