Binary Search Fundamentals - Master the Universal Template

Overview

Binary search is one of the most fundamental algorithms in computer science. It’s deceptively simple in concept yet notoriously tricky to implement correctly. Many experienced engineers still struggle with the details:

• Should right be initialized to n-1 or n?
• Is the loop condition left < right or left <= right?
• When updating, is it mid - 1 or just mid?
• Should I return left or right?

The good news: Once you understand the core principle, you can derive the correct implementation every time without memorizing multiple templates.

---

Core Insight: Finding the Boundary

The key insight is that all binary search problems reduce to finding a boundary:

Array:  [1] [2] [3] [5] [5] [5] [6] [7] [9]
Index:   0   1   2   3   4   5   6   7   8
                     ↑
                  boundary
       
Left region:  elements < 5  →  [1, 2, 3]
Right region: elements ≥ 5  →  [5, 5, 5, 6, 7, 9]

The boundary is the first position where the condition becomes true. Binary search efficiently finds this boundary by:

1. Shrinking the search range by half each iteration
2. Moving left to exclude elements that don’t satisfy the condition
3. Moving right to include elements that do satisfy the condition
4. When left > right, the search range is empty, and left points to the boundary

💡 Key Rule: The if condition matches what you’re searching for. If finding “first x ≥ target”, use if (nums[mid] >= target).

Visual Intuition

Initial:     [1, 2, 3, 5, 5, 5, 6, 7, 9]    target = 5
              L                       R

Step 1:      [1, 2, 3, 5, 5, 5, 6, 7, 9]    mid = 4, nums[4] = 5 >= 5 ✓
              L           M           R     → shrink right

Step 2:      [1, 2, 3, 5, 5, 5, 6, 7, 9]    mid = 1, nums[1] = 2 < 5 ✗
              L     M     R                 → shrink left

Step 3:      [1, 2, 3, 5, 5, 5, 6, 7, 9]    mid = 3, nums[3] = 5 >= 5 ✓
                    L  M  R                 → shrink right

Step 4:      [1, 2, 3, 5, 5, 5, 6, 7, 9]    left > right, return left = 3
                    L  R                    ✓ First 5 found at index 3

---

Finding Lower Bound (First x ≥ target)

The lower bound is the first element greater than or equal to the target. This is also the insert position if the target doesn’t exist.

💡 How It Works

We maintain a closed interval [left, right]:

1. If nums[mid] >= target, the answer might be at mid or to the left → shrink right
2. If nums[mid] < target, the answer must be to the right → shrink left
3. When left > right, left points to the lower bound

🎮 Interactive Visualization

Watch how left and right converge to find the first element ≥ target.

💻 Template Code

JavaScriptJavaPython

Loading...

✅ Key Points

When loop ends…	left points to…
Target exists	First occurrence of target
Target doesn’t exist	Where target should be inserted
All elements < target	n (past the end)

---

Finding Upper Bound (First x > target)

The upper bound is the first element strictly greater than the target.

💡 How It Works

Almost identical to lower bound, but change >= to >:

if (nums[mid] > target)   // > instead of >=

This means elements equal to target go to the left region, so we find the first element after all occurrences of target.

🎮 Interactive Visualization

Notice how the boundary moves past all elements equal to target.

💻 Template Code

JavaScriptJavaPython

Loading...

🔗 Relationship with Lower Bound

upperBound(target) = lowerBound(target + 1)   // for integers

Number of elements equal to target:

count = upperBound(target) - lowerBound(target)

---

Finding First Occurrence

To find the first occurrence of a specific value, use lower bound and verify:

🎮 Interactive Visualization

💻 Template Code

JavaScriptJavaPython

Loading...

---

Finding Last Occurrence

To find the last occurrence, we can:

1. Use upper bound and subtract 1, OR
2. Use the complementary condition >

🎮 Interactive Visualization

💻 Template Code

JavaScriptJavaPython

Loading...

🔍 Note on Return Value

For searchLast, we return right (not left) because:

• When finding “last x ≤ target”, elements ≤ target are pushed left
• right ends up pointing to the rightmost such element

---

Template Comparison: Closed vs Half-Open

There are two common styles for binary search. Both are correct; choose one and stick with it.

Closed Interval [left, right]

Aspect	Value
Initial right	n - 1
Loop condition	left <= right
Update right	mid - 1
When loop ends	left > right
Return for lower bound	left

Left-Closed, Right-Open [left, right)

Aspect	Value
Initial right	n
Loop condition	left < right
Update right	mid (no -1)
When loop ends	left == right
Return for lower bound	left or right

💻 Half-Open Template

JavaScriptJavaPython

Loading...

💡 Recommendation: The half-open interval has fewer edge cases. When the loop ends, left == right, so you can return either.

📊 Decision Guide

Scenario	Recommended Style
C++ STL style (lower_bound/upper_bound)	Half-open [l, r)
Direct target search	Closed [l, r]
Avoid off-by-one confusion	Half-open [l, r)
Finding exact match	Closed [l, r]

---

Interview Problems

Problem 1: Find First and Last Position (LC 34)

Problem: Given a sorted array, find the starting and ending position of a target value.

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

Input:  nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Solution: Combine searchFirst and searchLast:

JavaScriptJavaPython

Loading...

Complexity: O(log n) time, O(1) space

---

Problem 2: Search Insert Position (LC 35)

Problem: Given a sorted array and target, find the index where target should be inserted.

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

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

Solution: This is exactly lower bound — no code changes needed!

function searchInsert(nums, target) {
  return lowerBound(nums, target);
}

Complexity: O(log n) time, O(1) space

---

Problem 3: Search a 2D Matrix (LC 74)

Problem: Search for a target in an m×n matrix where:

• Each row is sorted in ascending order
• The first element of each row is greater than the last element of the previous row

Matrix:
[1,   3,  5,  7]
[10, 11, 16, 20]
[23, 30, 34, 60]

Target: 3 → true
Target: 13 → false

Key Insight: Treat the 2D matrix as a flattened 1D sorted array!

Flattened: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Index:      0  1  2  3   4   5   6   7   8   9  10  11

For index mid:
  row = mid / n
  col = mid % n

JavaScriptJavaPython

Loading...

Complexity: O(log(m×n)) time, O(1) space

Step-by-Step Example

Matrix (3×4):                  Target = 16
[1,   3,  5,  7]
[10, 11, 16, 20]
[23, 30, 34, 60]

Flattened view: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
                 0  1  2  3   4   5   6   7   8   9  10  11

Step 1: left=0, right=11, mid=5
        row=5/4=1, col=5%4=1 → matrix[1][1] = 11 < 16
        left = 6

Step 2: left=6, right=11, mid=8
        row=8/4=2, col=8%4=0 → matrix[2][0] = 23 > 16
        right = 7

Step 3: left=6, right=7, mid=6
        row=6/4=1, col=6%4=2 → matrix[1][2] = 16 == 16 ✓
        return true

---

Problem 4: Find the Distance Value Between Two Arrays (LC 1385)

Problem: Given two integer arrays arr1 and arr2, and an integer d, count how many elements arr1[i] exist such that for all elements arr2[j], |arr1[i] - arr2[j]| > d.

Input:  arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: 
  - arr1[0] = 4: |4-1|=3 > 2, |4-8|=4 > 2, |4-9|=5 > 2, |4-10|=6 > 2 ✓
  - arr1[1] = 5: |5-1|=4 > 2, |5-8|=3 > 2, |5-9|=4 > 2, |5-10|=5 > 2 ✓
  - arr1[2] = 8: |8-8|=0 ≤ 2 ✗

Input:  arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2

Core Insight:

The condition |arr1[i] - arr2[j]| > d for all j is equivalent to:

• No element exists in arr2 such that arr1[i] - d ≤ arr2[j] ≤ arr1[i] + d

So the problem becomes: Check if any element in arr2 falls within the range [arr1[i] - d, arr1[i] + d].

Key Optimization: Only one binary search needed!

1. Sort arr2
2. For each arr1[i], find the first element ≥ (arr1[i] - d) at position idx
3. Check if that element is ≤ (arr1[i] + d):
   • If yes, there’s an element in range → don’t count
   • If no (or idx out of bounds), no elements in range → count it

Why One Binary Search is Enough?

Sorted arr2:  [1,  8,  9,  10]
                   
Range [2, 6]:
              ----[======]----
              1   2      6  8 9 10
              ↑            ↑
           <Left          Right>
              
First element >= 2 is 8
8 > 6, so no elements in range ✓


Range [6, 10]:
              ----------[======]
              1         6  8 9 10
                           ↑
                    First >= 6
              
First element >= 6 is 8
8 <= 10, so elements exist in range ✗

Because the array is sorted, after finding the first candidate:

• If it’s in range → range has elements
• If it’s to the right → all following elements are larger, range is empty
• If none exists → all elements are to the left, range is empty

JavaScriptJavaPython

Loading...

Complexity: O(n log n + m log n) time (sort + m binary searches), O(1) space (excluding sort)

Step-by-Step Example

arr1 = [4, 5, 8], arr2 = [10, 9, 1, 8], d = 2
After sorting arr2 = [1, 8, 9, 10]

Process arr1[0] = 4:
  Range [4-2, 4+2] = [2, 6]
  idx = lowerBound(arr2, 2) = 1 (arr2[1] = 8)
  arr2[1] = 8 > 6 → no elements in range ✓
  result = 1

Process arr1[1] = 5:
  Range [5-2, 5+2] = [3, 7]
  idx = lowerBound(arr2, 3) = 1 (arr2[1] = 8)
  arr2[1] = 8 > 7 → no elements in range ✓
  result = 2

Process arr1[2] = 8:
  Range [8-2, 8+2] = [6, 10]
  idx = lowerBound(arr2, 6) = 1 (arr2[1] = 8)
  arr2[1] = 8 ≤ 10 → elements exist in range ✗
  result = 2 (unchanged)

Return 2

---

Common Pitfalls

1. Integer Overflow

❌ Bad:

const mid = (left + right) / 2;  // can overflow!

✅ Good:

const mid = left + Math.floor((right - left) / 2);

💡 In Java/C++, left + right can exceed INT_MAX. Always use the safe formula.

2. Infinite Loop

❌ Bad:

if (nums[mid] >= target) {
  right = mid;  // Wrong for closed interval!
}

With closed interval [left, right], if you don’t do mid - 1, the range might never shrink.

Example of infinite loop:

nums = [1, 2], target = 2
left = 0, right = 1, mid = 0
nums[0] = 1 < 2, so left = 1
left = 1, right = 1, mid = 1
nums[1] = 2 >= 2, right = mid = 1  // STUCK! left <= right forever

3. Off-by-One in Boundary Check

Always verify the result:

const idx = lowerBound(nums, target);
// Check bounds before accessing nums[idx]
if (idx < nums.length && nums[idx] === target) {
  // found
}

4. Wrong Return Value

Search Type	Return	Why
Lower bound	left	First in right region
Upper bound	left	First in right region
Search first	left (then verify)	Lower bound of target
Search last	right (then verify)	Upper bound - 1

5. Mixing Template Styles

❌ Don’t mix styles:

let left = 0, right = nums.length - 1;  // Closed style
while (left < right) {  // WRONG! This is half-open style
  // ...
}

✅ Be consistent:

// Closed interval: [left, right]
let left = 0, right = nums.length - 1;
while (left <= right) {
  right = mid - 1;  // or left = mid + 1
}

// Half-open interval: [left, right)
let left = 0, right = nums.length;
while (left < right) {
  right = mid;  // or left = mid + 1
}

---

Summary

🔑 The Universal Template

All binary search problems in sorted arrays follow this pattern:

while (left <= right) {
  const mid = left + Math.floor((right - left) / 2);
  if (/* condition matches what we seek */) {
    right = mid - 1;
  } else {
    left = mid + 1;
  }
}
return left;  // or right, depending on problem

📋 Quick Reference

Problem	Condition	Return
First x ≥ target	nums[mid] >= target	left
First x > target	nums[mid] > target	left
Last x ≤ target	nums[mid] > target	right
Last x < target	nums[mid] >= target	right

💡 Key Takeaways

1. Think in boundaries: Binary search finds where a condition becomes true
2. Match condition to goal: The if condition should match what you’re searching for
3. Choose one style: Either closed [l,r] or half-open [l,r), but be consistent
4. Verify results: Always check if the returned index is valid and matches the target

🎯 Interview Tip: When asked a binary search question, first identify what “condition” you’re searching for, then apply the template. Practice explaining your thought process out loud!

📚 Next Steps

Ready for more advanced binary search? Check out Binary Search Advanced: The Two-Segment Property to learn how binary search works on unsorted arrays like rotated arrays and peak finding!