🔍 Binary Search Pattern – The Interviewer's Favorite

🧠 TL;DR - What to Focus On

This guide is long — but structured. Use the Table of Contents (TOC) as your best friend to glance, skim, or jump around. Here's where to go based on your goal:

✅ Just want the templates and patterns? → Jump to 🧪 Use Cases & Problem Templates
Includes 5 reusable binary search patterns with Java code and dry runs.

⚠️ Keep messing up edge cases or stuck in infinite loops? → Read ❗ Common Pitfalls: Infinite Loops and Off-by-One Errors
Covers loop conditions, shrinking logic, and off-by-one traps that haunt beginners.

🤯 Struggling with "Binary Search on Answer" problems? → Start with 🔧 Core Template: Binary Search on Answer
→ Then go through 🧠 How to Recognize & Apply Binary Search on Answer
→ Learn by example via Template 4 and Template 5

🧘 Want a high-level recap at the end? → Skip to 🧠 Key Takeaways

Introduction

Binary Search helps cut down search space logarithmically by halving the range each time. It works best when you're dealing with:

A sorted array, or
A monotonic decision space (increasing/decreasing answers)

Instead of brute-forcing through every possibility, we jump straight to the middle, ask "too big or too small?" and shrink our space accordingly.

📌 When to Use Binary Search

Reach for this pattern when:

✅ You're working with a sorted array
✅ You're searching for a target value or threshold
✅ You can define a “yes/no” decision function to guide the direction
✅ The answer lies in a range of values rather than an index

⚙️ The Two Faces of Binary Search

There are two major flavors of Binary Search you'll encounter:

1. Classic Index Binary Search

Works directly on a sorted array to locate a specific element (or its left/right boundary).

Examples:
- Exact search (find a number)
- Leftmost/rightmost position of target
- Insert position
2. Binary Search on Answer

You don’t binary search an array, but a range of potential answers. At each step, you ask:
“Can this value work as the answer?”
Then adjust your bounds based on a predicate.
Examples:
- Minimum speed, capacity, time, or size
- Works when you can simulate and validate a guess

🧰 Core Binary Search Template

 int left = 0, right = arr.length - 1;

 while (left <= right) {
     int mid = left + (right - left) / 2;

     if (arr[mid] == target) return mid;
     else if (arr[mid] < target) left = mid + 1;
     else right = mid - 1;
 }
 return -1;

This is the classic search in a sorted array.
Edge tweaks lead to all sorts of variants — leftmost, rightmost, first failing value, etc.

❗ Common Pitfalls: Infinite Loops and Off-by-One Errors

Binary Search is simple in theory — but off-by-one bugs and infinite loops haunt beginners. Let’s clear it up once and for all.

🔁 Loop Conditions

Condition	Use When You...
`while (left <= right)`	Want to check `mid` as a valid index (Classic style)
`while (left < right)`	Want to stop at the first valid value (Answer style)

❌ Never write: left = mid or right = mid ✅ Always shrink the range: left = mid + 1 or right = mid - 1

💥 Why Infinite Loops Happen

They occur when your left and right don’t move. Example mistake:

// ❌ This can loop forever if mid == left 
if (nums[mid] < target) left = mid;

Fix: Use left = mid + 1 to ensure the window shrinks.

🧠 Mental Model: “Always Shrink the Window”

Every iteration must cut off part of the search space. If mid doesn't eliminate anything, you’re stuck in a loop.

Before: 
[ ... L ... M ... R ] 
After: 
[ ... L ... M ] ✅  or  [ ... M ... R ] ✅ 

❌ [ ... L ... M ... R ]  ← window never shrinks

🔧 Core Template: Binary Search on Answer

 int left = MIN_POSSIBLE, right = MAX_POSSIBLE;

 while (left < right) {
     int mid = left + (right - left) / 2;

     if (isValid(mid)) {
         right = mid;  Try smaller
     } else {
         left = mid + 1;  Need larger
     }
 }
 return left;

Note that in these problems:

You don’t have an array
You simulate a decision at mid using a predicate like isValid(mid)

🧠 How to Recognize & Apply Binary Search on Answer

Binary Search isn't just for sorted arrays — it shines in optimization problems too.

When you're not given a sorted array but are asked to minimize or maximize a value, you're likely in Binary Search on Answer territory.

🧭 Step 1: Spot the Clues

These are the telltale signs you’re meant to binary search over the answer itself:

Clue	What It Looks Like
✅ You're asked to minimize or maximize a number	“What is the minimum time to finish…?”
✅ You can “guess a number and check if it works”	Can simulate using `isValid(mid)`
✅ There’s a monotonic relationship in your guesses	If 5 works, 6 might also work — or vice versa
✅ You're not searching an array but a value range	Usually from `1` to `max(input)`
✅ Brute force is too slow	Constraints are large (N = 10⁵), but value space is small

🔧 How to Build the Feasibility Function (`isValid(mid)`)

This is the core trick of Binary Search on Answer:
You don’t know the answer, so you guess it, simulate the scenario, and ask:

“If I set the answer to mid, can I make it work?”

✅ Step 1: Treat `mid` as a guess

This is the “what if?” moment.

“What if Koko eats mid bananas per hour?”
“What if the ship has mid capacity?”
“What if I assign tasks with max load mid?”

✅ Step 2: Simulate based on the problem

Write a simulation that models the system using that mid guess.
Can you:

Finish in time?
Fit everything in?
Use valid number of splits/days?

✅ Step 3: Return true or false

If the simulation succeeds, mid is feasible → you can try better
If it fails, it's too extreme → adjust your search accordingly

🧪 Example: Koko Eating Bananas

 boolean isValid(int speed) {
     int hours = 0;
     for (int pile : piles) {
         hours += Math.ceil((double) pile / speed);
     }
     return hours <= h;
 }

If speed is high → time taken is less → more likely to be valid
Monotonic behavior → good for binary search

🧪 Example: Ship Packages in D Days

 boolean isValid(int capacity) {
     int days = 1, current = 0;
     for (int weight : weights) {
         if (current + weight > capacity) {
             days++;
             current = 0;
         }
         current += weight;
     }
     return days <= D;
 }

If capacity is high → you need fewer days → valid
The more you increase capacity, the better it gets → again, monotonic

🔄 Why Monotonicity Matters

Binary Search only works if:

All values left of X are invalid, and all values right of X are valid (or vice versa)

That’s what lets you cut the space in half and be confident.

🧘 Summary: How to Think

“If I guess this number, can I make it work?”

If yes → it’s feasible → try to optimize further
If no → guess again with a new range

🧪 Use Cases & Problem Templates

Let’s now explore this pattern across classic problems, one template per pattern.

Each one will include:

🔹 Problem
🔹 Goal
🔹 What we would do
🔹 Template code
🔹 Step-by-step dry run
🔁 Followed by: Other problems that use the same approach with a twist

📘 Template #1: Classic Binary Search

Representative Problem: Binary Search – Leetcode #704

🔹 Problem

Given a sorted integer array nums and an integer target, return the index if the target is found. If not, return -1.

🔹 Goal

Find the exact position of target using binary search.

🔹 What we would do

Use the standard binary search template with left <= right. Keep narrowing the range by comparing nums[mid] to target.

🔹 Template Code

int search(int[] nums, int target) { 
    int left = 0, 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; 
}

🔹 Dry Run

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9 

Initial: left = 0, right = 5 
Step 1: mid = 2 → nums[2] = 3 → too small → left = 3 
Step 2: mid = 4 → nums[4] = 9 → match! return 4

🔁 Other Famous Problems Using This Template

📌 Peak Index in a Mountain Array (#852)

Twist: You're not looking for an exact value — you're trying to find the peak in a mountain array (first increasing, then decreasing).
Observation: If nums[mid] > nums[mid + 1], you're in the descending half, so the peak lies on the left side or at mid.
Else, you're in the ascending half, so move right.
Same binary search structure, but guided by slope direction, not equality.

📌 Find Minimum in Rotated Sorted Array (#153)

Twist: The array is sorted but rotated, so it’s not fully monotonic. You’re trying to find the minimum element, not a target.
Key idea: One half of the array is always sorted. Compare nums[mid] with nums[right] to decide which half contains the minimum.
If nums[mid] > nums[right], the min must be to the right of mid.
If nums[mid] <= nums[right], the min could be at or to the left of mid.
Still classic binary search logic: shrink your bounds based on comparisons.

📌 Guess Number Higher or Lower (#374)

Twist: You don’t access the array directly — instead, you get feedback via an API (guess(mid) returns -1/0/1).
It behaves exactly like a binary search comparator:
- 0 → target found
- -1 → guess is too high
- 1 → guess is too low
It's a textbook binary search — only difference is using an external check instead of direct comparison.

📘 Template #2: Search Insert Position

Representative Problem: Search Insert Position – Leetcode #35

🔹 Problem

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

🔹 Goal

Find the correct position to insert target such that array remains sorted.

🔹 What we would do

We’re not just checking for equality — we need the first position ≥ target. So, we don’t stop when we find the target — we keep shrinking towards the left boundary. Use left < right style binary search to converge on the correct index.

🔹 Template Code

int searchInsert(int[] nums, int target) { 
    int left = 0, right = nums.length; 

    while (left < right) { 
        int mid = left + (right - left) / 2; 

        if (nums[mid] < target) left = mid + 1; 
        else right = mid; 
    } 

    return left; 
}

🔹 Dry Run

Input: nums = [1, 3, 5, 6], target = 5 

Initial: left = 0, right = 4 
Step 1: mid = 2 → nums[2] = 5 → right = 2 
Step 2: mid = 1 → nums[1] = 3 → left = 2 
left == right → return 2 

✅ Target found at index 2

Input: nums = [1, 3, 5, 6], target = 2 

Initial: left = 0, right = 4 
Step 1: mid = 2 → nums[2] = 5 → right = 2 
Step 2: mid = 1 → nums[1] = 3 → right = 1 
Step 3: mid = 0 → nums[0] = 1 → left = 1 
left == right → return 1 

✅ Insert position for target = 2 is index 1

🔁 Other Famous Problems Using This Template

📌 Search Insert Position (#35)

This is the canonical example of lower_bound.
Find the index where target should be inserted — i.e., first element ≥ target.

📌 Smallest Letter Greater Than Target (#744)

Twist: Find the next character strictly greater than the target.
Equivalent to upper_bound — first element > target.
Wrap-around behavior handled using: letters[left % n].

📌 Find Right Interval (#436)

Twist: For each interval, find another interval starting at or after the current interval’s end.
You binary search over sorted start points → lower_bound logic on interval start.

📌 First and Last Position of Element in Sorted Array (#34)

Twist: Combines both lower_bound and upper_bound manually.
Binary search to find:
- First occurrence of target (left bound)
- First index > target, then subtract 1 for right bound

📘 Template #3: First and Last Position

Representative Problem: Find First and Last Position of Element in Sorted Array – Leetcode #34

🔹 Problem

Given a sorted array of integers and a target value, return the indices of the first and last occurrence of the target. If the target is not present, return [-1, -1].

🔹 Goal

Perform two binary searches:

To find the leftmost index of target (first occurrence)
To find the rightmost index of target (last occurrence)

🔹 What we would do

Use a modified binary search:

For the first occurrence, keep shrinking right even after finding the target
For the last occurrence, keep expanding right even after finding the target This is essentially combining lower_bound and upper_bound - 1.

🔹 Template Code

int[] searchRange(int[] nums, int target) { 
    int left = findBound(nums, target, true); 
    int right = findBound(nums, target, false); 
    return new int[]{left, right}; 
} 

int findBound(int[] nums, int target, boolean first) { 
    int left = 0, right = nums.length - 1, result = -1; 

    while (left <= right) { 
        int mid = left + (right - left) / 2; 

        if (nums[mid] == target) { 
            result = mid; 
            if (first) right = mid - 1; 
            else left = mid + 1; 
        } else if (nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        } 
    } 

    return result; 
}

🔹 Dry Run

Input: nums = [5, 7, 7, 8, 8, 10], target = 8 

First pass (first = true): 
Initial: left = 0, right = 5 
Step 1: mid = 2 → nums[2] = 7 → left = 3 
Step 2: mid = 4 → nums[4] = 8 → result = 4, right = 3 
Step 3: mid = 3 → nums[3] = 8 → result = 3, right = 2 
Ends: left = 3, right = 2 → left bound = 3 

Second pass (first = false): 
Initial: left = 0, right = 5 
Step 1: mid = 2 → nums[2] = 7 → left = 3 
Step 2: mid = 4 → nums[4] = 8 → result = 4, left = 5 
Step 3: mid = 5 → nums[5] = 10 → right = 4 
Ends: left = 5, right = 4 → right bound = 4 

Output: [3, 4]

🔁 Other Famous Problems Using This Template

📌 [Count Occurrences of a Number in Sorted Array – Binary Search Variant]

Not an official Leetcode title, but the technique is used in multiple places.
Run findBound(..., true) and findBound(..., false)
Count = (right - left) + 1 if both bounds are valid.

📌 [Number of Occurrences of a Number in a Sorted Array – Similar to GFG/LC Explore cards]

Same binary search twice — one for left boundary, one for right boundary.
Used inside frequency-based search problems and subarray counting variations.

📌 First Bad Version (#278)

Twist: Instead of a target value, you’re given a isBadVersion(mid) API.
The goal is to find the first position where the condition becomes true — like a custom lower_bound.
One binary search to find the earliest valid index.

📘 Template #4: Binary Search on Answer

Representative Problem: Koko Eating Bananas – Leetcode #875

🔹 Problem

Koko has piles[] of bananas and h hours to finish them. Each hour, she picks one pile and eats up to k bananas (k is the speed you pick). If a pile has fewer than k, she eats the whole pile and waits till next hour. Return the minimum integer speed k so she can eat all bananas in h hours.

🔹 Goal

Find the smallest possible speed k such that total eating time ≤ h.

🔹 What we would do

This is the classic Binary Search on Answer pattern:

You're not given a sorted array, but you can guess an answer (a speed)
You simulate that guess using a function like canEatAll(k)
The faster Koko eats, the fewer hours she takes → monotonic decreasing function
Use binary search over the speed range 1 to max(piles)

🔹 Template Code

int minEatingSpeed(int[] piles, int h) { 
    int low = 1, high = Arrays.stream(piles).max().getAsInt(); 

    while (low < high) { 
        int mid = (low + high) / 2; 
        if (canEatAll(piles, h, mid)) { 
            high = mid; // Try smaller speed 
        } else { 
            low = mid + 1; // Need more speed 
        } 
    } 

    return low; 
} 

boolean canEatAll(int[] piles, int h, int speed) { 
    int hours = 0; 
    for (int pile : piles) { 
        hours += (pile + speed - 1) / speed; // Ceil division 
    } 
    return hours <= h; 
}

🔹 Dry Run

Input: piles = [3, 6, 7, 11], h = 8 

Speed search range: 1 to 11 
We want the **minimum speed** that works. 

Step 1: mid = (1 + 11) / 2 = 6 
    Total hours: 1 + 1 + 2 + 2 = 6 ✅ valid → try smaller → high = 6 

Step 2: mid = (1 + 6) / 2 = 3 
    Total hours: 1 + 2 + 3 + 4 = 10 ❌ too much → low = 4 

Step 3: mid = (4 + 6) / 2 = 5 
    Hours: 1 + 2 + 2 + 3 = 8 ✅ valid → high = 5 

Step 4: mid = (4 + 5) / 2 = 4 
    Hours: 1 + 2 + 2 + 3 = 8 ✅ valid → high = 4 

low == high → return 4 ✅ 

Answer: 4

🔁 Other Famous Problems Using This Template

📌 Capacity To Ship Packages in D Days (#1011)

You binary search over ship capacity, and use canShip(capacity) to simulate shipping timeline.

📌 Split Array Largest Sum (#410)

Binary search over possible largest subarray sums.
Feasibility check is whether you can split array into k parts without exceeding that sum.

📌 Minimum Number of Days to Make m Bouquets (#1482)

You guess a day, and check if it’s possible to form m bouquets of size k.
Binary search over days, with a bloom check.

📌 Find the Smallest Divisor Given a Threshold (#1283)

Find the minimum divisor such that sum of ceiling divisions ≤ threshold.

📌 [Aggressive Cows (GFG / InterviewBit)]

Maximize the minimum distance between cows.
Use binary search on distance, and place cows greedily to check feasibility.

📘 Template #5: Binary Search on Real Numbers (Precision Search)

Sometimes the problem asks for a decimal answer with precision, like square root or speed with floating-point constraints.

In such problems:

You’re not dealing with integers
You can’t use left < right because floats never truly “meet”
You fix it by running the loop for a number of iterations (usually 100)

🔹 Problem

Return the square root of n as a decimal accurate to 5–6 digits.

🔹 What we would do

Binary search in the range [0, n]
For each guess mid, check: mid * mid <= n
Move left or right based on that
After ~100 steps, left will be close to √n

🔹 Template Code

double sqrt(int n) { 
    double left = 0, right = n, mid = 0; 
    for (int i = 0; i < 100; i++) { 
        mid = (left + right) / 2.0; 
        if (mid * mid > n) { 
            right = mid;  // Too big, shrink from right 
        } else { 
            left = mid;   // Too small or just right, move up 
        } 
    } 
    return left; 
}

🔹 Dry Run (n = 10)

We want to compute √10 ≈ 3.16227 

Initial: left = 0.0, right = 10.0 

Iteration 1: 
  mid = 5.0 → 5*5 = 25 > 10 → shrink right → right = 5.0 

Iteration 2: 
  mid = 2.5 → 2.5*2.5 = 6.25 < 10 → grow left → left = 2.5 

Iteration 3: 
  mid = 3.75 → 14.06 > 10 → shrink right → right = 3.75 

Iteration 4: 
  mid = 3.125 → 9.77 < 10 → grow left → left = 3.125 

Iteration 5: 
  mid = 3.4375 → 11.82 > 10 → shrink right → right = 3.4375 

Iteration 6: 
  mid = 3.28125 → 10.76 > 10 → shrink right → right = 3.28125 

Iteration 7: 
  mid = 3.203125 → 10.25 > 10 → shrink right → right = 3.203125 

Iteration 8: 
  mid = 3.1640625 → 10.01 > 10 → shrink right → right = 3.1640625 

Iteration 9: 
  mid = 3.14453125 → 9.89 < 10 → grow left → left = 3.14453125 

... 

(This continues for 100 iterations, zooming in on √10) 

Final left ≈ 3.16227 ✅

🔍 You’ll eventually converge to a value where mid * mid is extremely close to n (like 9.9999996 for n = 10), accurate to 5–6 decimal places.

🔁 Other Famous Problems Using This Template

📌 Minimum Speed to Arrive on Time (#1870)

Problem: You’re given distances and a total time limit. You must return the minimum integer speed that allows you to arrive on time.
What we’re searching for: The smallest speed s such that total travel time ≤ hour.
Feasibility Check: Simulate time = sum of ceil(dist[i] / s) for all but last leg, and exact for last leg.
Why it’s binary search: Higher speed → less time → monotonic decreasing function.
Decimal twist: If hour is not an integer (e.g. 1.5), we’re essentially comparing float sums, which means we must handle floating point error carefully.

📌 Kth Smallest Distance Pair (#719)

Problem: Given an array, return the k-th smallest absolute difference between any two elements.
What we’re searching for: The smallest distance d such that there are at least k pairs with diff ≤ d.
Feasibility Check: For each mid guess (distance), use two pointers to count number of valid pairs with distance ≤ mid.
Why it’s binary search: As distance d increases, the number of valid pairs also increases → monotonic relationship.
Why real number template applies: In some variations, especially with coordinates or weights, the distances can be floating points. You’d binary search over decimal distances with precision.

📌 [Find Square Root of a Number – GFG / Custom Inputs]

Problem: Return the square root of a non-negative number n with decimal precision.
What we’re searching for: A double value x such that x * x is as close to n as possible.
Feasibility Check: If x * x > n, you’re too high → shrink right. Otherwise, grow left.
Why it’s binary search: It’s a classic case where we use binary search on a continuous domain (double) instead of an array.
Why use 100 iterations: Because floating point precision is tricky, instead of checking exact equality, we loop a fixed number of times to guarantee convergence.

🧠 Think: “Decimal answer? Fixed number of steps. Shrink the range slowly.”

🧠 Key Takeaways

Here are the 5 most important things to master about Binary Search for coding interviews:

🔁 Binary Search ≠ Only Searching Arrays
It's a mindset — use it to search over answers, floats, or any monotonic space, not just array indices.
🎯 Master the 5 Core Templates
Know when to use:
- Classic index lookup
- Insert position
- Left/right boundary
- Binary Search on Answer
- Precision-based (decimal) binary search
⚠️ Loop Boundaries Matter More Than You Think
Understand the difference between left <= right and left < right, and never write left = mid.
🧪 "Binary Search on Answer" Is the Real Interview MVP
Use it when you're asked to minimize/maximize under a constraint — like speed, time, load, capacity, etc.
Implement isValid(mid) to guide the search.
🧠 Dry Run Edge Cases Like a Pro
Interviewers love corner cases. Always dry run:
- Empty input
- Single-element arrays
- Target not found
- Off-by-one traps in even/odd length inputs
Conclusion

Once solid with this pattern, you can start spotting it in problems that don’t even look like binary search problems at first. Hope this helps internalize/revise Binary Search pattern for interviews!

DSA Patterns: Binary Search

Table of contents

🔍 Binary Search Pattern – The Interviewer's Favorite

🧠 TL;DR - What to Focus On

Introduction

📌 When to Use Binary Search

⚙️ The Two Faces of Binary Search

1. Classic Index Binary Search

2. Binary Search on Answer

🧰 Core Binary Search Template

❗ Common Pitfalls: Infinite Loops and Off-by-One Errors

🔁 Loop Conditions

💥 Why Infinite Loops Happen

🧠 Mental Model: “Always Shrink the Window”

🔧 Core Template: Binary Search on Answer

🧠 How to Recognize & Apply Binary Search on Answer

🧭 Step 1: Spot the Clues

🔧 How to Build the Feasibility Function (isValid(mid))

✅ Step 1: Treat mid as a guess

✅ Step 2: Simulate based on the problem

✅ Step 3: Return true or false

🧪 Example: Koko Eating Bananas

🧪 Example: Ship Packages in D Days

🔄 Why Monotonicity Matters

🧘 Summary: How to Think

🧪 Use Cases & Problem Templates

📘 Template #1: Classic Binary Search

🔹 Problem

🔹 Goal

🔹 What we would do

🔹 Template Code

🔹 Dry Run

🔁 Other Famous Problems Using This Template

📘 Template #2: Search Insert Position

🔹 Problem

🔹 Goal

🔹 What we would do

🔹 Template Code

🔹 Dry Run

🔁 Other Famous Problems Using This Template

📘 Template #3: First and Last Position

🔹 Problem

🔹 Goal

🔹 What we would do

🔹 Template Code

🔹 Dry Run

🔁 Other Famous Problems Using This Template

📘 Template #4: Binary Search on Answer

🔹 Problem

🔹 Goal

🔹 What we would do

🔹 Template Code

🔹 Dry Run

🔁 Other Famous Problems Using This Template

📘 Template #5: Binary Search on Real Numbers (Precision Search)

🔹 Problem

🔹 What we would do

🔹 Template Code

🔹 Dry Run (n = 10)

🔁 Other Famous Problems Using This Template

🧠 Key Takeaways

Conclusion

Subscribe to my newsletter

LilSardarX

LilSardarX

🔧 How to Build the Feasibility Function (`isValid(mid)`)

✅ Step 1: Treat `mid` as a guess