Binary Search Loop Conditions: The Complete Guide

Table of Contents

1. The Two Main Patterns
2. Pattern 1: Exact Match (left <= right)
3. Pattern 2: Finding Boundaries (left < right)
4. Decision Tree: Which Pattern to Use
5. Common Mistakes and How to Avoid Them
6. Practice Problems by Pattern

---

The Two Main Patterns {#two-patterns}

Binary search has two fundamental patterns that differ in their loop conditions and boundary handling:

Pattern	Loop Condition	Initialization	When to Use
Pattern 1	left <= right	right = n - 1	Finding exact match
Pattern 2	left < right	right = n or n - 1	Finding boundaries/position

Visual Comparison

// PATTERN 1: Exact Match
function pattern1(arr, target) {
    let left = 0;
    let right = arr.length - 1;  // INCLUSIVE boundary
    
    while (left <= right) {       // <= allows checking single element
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) {
            left = mid + 1;       // Exclude mid
        } else {
            right = mid - 1;      // Exclude mid
        }
    }
    return -1;
}

// PATTERN 2: Find Boundary
function pattern2(arr, target) {
    let left = 0;
    let right = arr.length;       // EXCLUSIVE boundary (or n-1)
    
    while (left < right) {        // < stops when converged
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] < target) {
            left = mid + 1;       // Exclude mid
        } else {
            right = mid;          // Include mid (could be answer)
        }
    }
    return left;                  // left === right at this point
}

---

Pattern 1: Exact Match (left <= right) {#pattern-1}

When to Use

Use left <= right when you want to:

• ✅ Find an exact match of a target
• ✅ Return -1 if not found
• ✅ Exclude mid in both directions after comparison

Key Characteristics

let left = 0;
let right = arr.length - 1;  // INCLUSIVE (can access arr[right])

while (left <= right) {      // Continue until search space is empty
    const mid = Math.floor(left + (right - left) / 2);
    
    if (arr[mid] === target) {
        return mid;           // Found it!
    }
    
    if (arr[mid] < target) {
        left = mid + 1;       // Must exclude mid
    } else {
        right = mid - 1;      // Must exclude mid
    }
}

return -1;                    // Not found

Why <=?

The <= allows the loop to check the last remaining element when left === right.

Example walkthrough:

arr = [1, 2, 3, 4, 5], target = 5

Initial: left=0, right=4
Step 1:  mid=2, arr[2]=3 < 5, left=3, right=4
Step 2:  mid=3, arr[3]=4 < 5, left=4, right=4
Step 3:  mid=4, arr[4]=5 === 5 ✓ FOUND!
         ^
         This step only happens because left <= right (4 <= 4)

Complete Examples

Example 1: Basic Binary Search

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] === target) return mid;
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// Test
console.log(binarySearch([1, 3, 5, 7, 9], 7));  // 3
console.log(binarySearch([1, 3, 5, 7, 9], 6));  // -1

Example 2: Search in Rotated Array

function searchRotated(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (nums[mid] === target) return mid;
        
        // Determine which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

// Test
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0));  // 4

Example 3: Find Peak Element (using Pattern 1)

function findPeakElement(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        // Check if mid is a peak
        const leftVal = mid > 0 ? nums[mid - 1] : -Infinity;
        const rightVal = mid < nums.length - 1 ? nums[mid + 1] : -Infinity;
        
        if (nums[mid] > leftVal && nums[mid] > rightVal) {
            return mid;  // Found peak
        }
        
        // Move towards the higher neighbor
        if (rightVal > nums[mid]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
}

---

Pattern 2: Finding Boundaries (left < right) {#pattern-2}

When to Use

Use left < right when you want to:

• ✅ Find first/last position of something (boundary)
• ✅ Find insertion point (lower/upper bound)
• ✅ Keep mid as a candidate answer (right = mid)
• ✅ Return a position rather than found/not-found

Key Characteristics

// Option A: Exclusive right boundary
let left = 0;
let right = arr.length;      // EXCLUSIVE (cannot access arr[right])

// Option B: Inclusive right boundary  
let left = 0;
let right = arr.length - 1;  // INCLUSIVE (can access arr[right])

while (left < right) {        // Stop when left === right (converged)
    const mid = Math.floor(left + (right - left) / 2);
    
    if (condition) {
        left = mid + 1;       // Exclude mid
    } else {
        right = mid;          // KEEP mid as candidate!
    }
}

return left;                  // left === right, the answer

Why < and not <=?

The < stops when left and right converge to the same position, which is your answer.

Example walkthrough:

arr = [1, 2, 2, 2, 3], target = 2 (find first occurrence)

Initial: left=0, right=5
Step 1:  mid=2, arr[2]=2 >= 2, right=2, left=0
Step 2:  mid=1, arr[1]=2 >= 2, right=1, left=0
Step 3:  mid=0, arr[0]=1 < 2,  left=1, right=1
         Now left === right, exit loop
         Answer: left=1 (first occurrence of 2)

Two Variations of Pattern 2

Variation A: right = n (Exclusive Upper Bound)

function lowerBound(arr, target) {
    let left = 0;
    let right = arr.length;  // EXCLUSIVE: arr[right] doesn't exist
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;      // mid could be the answer
        }
    }
    
    return left;              // First position >= target
}

// Works for insertion points beyond array
console.log(lowerBound([1, 2, 4, 5], 3));  // 2 (insert before 4)
console.log(lowerBound([1, 2, 4, 5], 6));  // 4 (insert at end)

Variation B: right = n - 1 (Inclusive Upper Bound)

function lowerBoundInclusive(arr, target) {
    let left = 0;
    let right = arr.length - 1;  // INCLUSIVE: arr[right] exists
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    // Check if found
    return (left < arr.length && arr[left] >= target) ? left : -1;
}

Complete Examples

Example 1: Lower Bound (First Position >= Target)

function lowerBound(arr, target) {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;      // arr[mid] >= target, keep as candidate
        }
    }
    
    return left;
}

// Test
console.log(lowerBound([1, 2, 2, 2, 3, 4], 2));  // 1 (first 2)
console.log(lowerBound([1, 2, 2, 2, 3, 4], 5));  // 6 (insertion point)

Example 2: Upper Bound (First Position > Target)

function upperBound(arr, target) {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] <= target) {  // Notice: <= instead of <
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

// Test
console.log(upperBound([1, 2, 2, 2, 3, 4], 2));  // 4 (position after last 2)

Example 3: Find First and Last Position

function searchRange(arr, target) {
    function findFirst() {
        let left = 0;
        let right = arr.length;
        
        while (left < right) {
            const mid = Math.floor(left + (right - left) / 2);
            
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    function findLast() {
        let left = 0;
        let right = arr.length;
        
        while (left < right) {
            const mid = Math.floor(left + (right - left) / 2);
            
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left - 1;
    }
    
    const first = findFirst();
    
    if (first >= arr.length || arr[first] !== target) {
        return [-1, -1];
    }
    
    const last = findLast();
    return [first, last];
}

// Test
console.log(searchRange([5, 7, 7, 8, 8, 10], 8));  // [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6));  // [-1, -1]

Example 4: Peak in Mountain Array

function peakIndexInMountainArray(arr) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] < arr[mid + 1]) {
            // Ascending, peak is to the right
            left = mid + 1;
        } else {
            // Descending or peak, could be at mid
            right = mid;
        }
    }
    
    return left;  // left === right at peak
}

// Test
console.log(peakIndexInMountainArray([0, 1, 0]));        // 1
console.log(peakIndexInMountainArray([0, 2, 1, 0]));     // 1
console.log(peakIndexInMountainArray([0, 10, 5, 2]));    // 1

Example 5: Minimum in Rotated Sorted Array

function findMin(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (nums[mid] > nums[right]) {
            // Minimum is in right half
            left = mid + 1;
        } else {
            // Minimum is in left half (including mid)
            right = mid;
        }
    }
    
    return nums[left];
}

// Test
console.log(findMin([3, 4, 5, 1, 2]));     // 1
console.log(findMin([4, 5, 6, 7, 0, 1, 2])); // 0

Example 6: Binary Search on Answer - Koko Eating Bananas

function minEatingSpeed(piles, h) {
    function canFinish(speed) {
        let hours = 0;
        for (const pile of piles) {
            hours += Math.ceil(pile / speed);
        }
        return hours <= h;
    }
    
    let left = 1;
    let right = Math.max(...piles);
    
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (canFinish(mid)) {
            right = mid;  // mid works, try smaller
        } else {
            left = mid + 1;  // mid doesn't work, need bigger
        }
    }
    
    return left;
}

// Test
console.log(minEatingSpeed([3, 6, 7, 11], 8));  // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5));  // 30

---

Decision Tree: Which Pattern to Use {#decision-tree}

Are you looking for an EXACT element?
│
├─ YES: Looking for exact match
│  │
│  └─ Use PATTERN 1
│     • left <= right
│     • right = n - 1
│     • return -1 if not found
│     • Examples: basic search, search in rotated array
│
└─ NO: Looking for position/boundary
   │
   └─ Use PATTERN 2
      • left < right
      • right = n or n - 1
      • return left (the converged position)
      • Examples: lower/upper bound, peak, min in rotated array,
                 binary search on answer

Quick Reference Table

Question Type	Pattern	Loop	Right Init	Update Right	Return
Find exact element	1	<=	n - 1	mid - 1	-1 or mid
First occurrence	2	<	n	mid	left
Last occurrence	2	<	n	mid	left - 1
Insertion point	2	<	n	mid	left
Peak element	2	<	n - 1	mid	left
Minimum in rotated	2	<	n - 1	mid	left
BS on answer	2	<	max	mid	left

---

Common Mistakes and How to Avoid Them {#common-mistakes}

Mistake 1: Infinite Loop with left = mid

Problem:

// WRONG! Can cause infinite loop
while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (condition) {
        left = mid;  // ⚠️ Dangerous!
    } else {
        right = mid - 1;
    }
}

Why it fails: When left = 1, right = 2, mid becomes 1, and if condition is true, left = mid = 1 creates an infinite loop.

Solutions:

// Solution 1: Always use mid + 1 for left
while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (condition) {
        left = mid + 1;  // ✓ Always makes progress
    } else {
        right = mid;
    }
}

// Solution 2: Use ceiling division for mid when using left = mid
while (left < right) {
    const mid = Math.floor((left + right + 1) / 2);  // Ceiling
    
    if (condition) {
        left = mid;  // ✓ Safe now
    } else {
        right = mid - 1;
    }
}

Mistake 2: Wrong Condition with Wrong Pattern

Problem:

// WRONG! Using Pattern 2 loop with Pattern 1 logic
let left = 0;
let right = arr.length - 1;

while (left < right) {  // Pattern 2 loop
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    
    if (arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;  // ⚠️ Pattern 1 update!
    }
}

// May miss the last element when left === right

Fix:

// Match the pattern throughout
let left = 0;
let right = arr.length - 1;

while (left <= right) {  // ✓ Pattern 1
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    
    if (arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;  // ✓ Consistent
    }
}

Mistake 3: Forgetting Edge Case Checks

Problem:

function findFirst(arr, target) {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;  // ⚠️ Might be out of bounds or wrong element!
}

Fix:

function findFirst(arr, target) {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    // ✓ Verify the result
    if (left < arr.length && arr[left] === target) {
        return left;
    }
    return -1;
}

Mistake 4: Integer Overflow (Less common in JS but good practice)

Problem:

const mid = Math.floor((left + right) / 2);  // Can overflow in other languages

Best Practice:

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

Mistake 5: Using right = n with left <= right

Problem:

// WRONG! Accessing arr[right] when right = n
let left = 0;
let right = arr.length;  // right is out of bounds!

while (left <= right) {  // Will try to access arr[n]
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;  // ⚠️ arr[n] is undefined!
    // ...
}

Fix:

// If using left <= right, use right = n - 1
let left = 0;
let right = arr.length - 1;  // ✓ In bounds

while (left <= right) {
    // ...
}

// OR if using right = n, use left < right
let left = 0;
let right = arr.length;  // Out of bounds

while (left < right) {  // ✓ Won't access arr[right]
    // ...
}

---

Practice Problems by Pattern {#practice-problems}

Pattern 1 Problems (left <= right, exact match)

1. Binary Search (LeetCode 704)

   • Find exact element in sorted array

2. Search in Rotated Sorted Array (LeetCode 33)

   • Find element in rotated array

3. Find Minimum in Rotated Sorted Array (LeetCode 153) *

   • Can use either pattern, but Pattern 1 works

4. Search a 2D Matrix (LeetCode 74)

   • Treat as 1D sorted array

5. Valid Perfect Square (LeetCode 367)

   • Find if number is perfect square

Pattern 2 Problems (left < right, find boundary)

1. First Bad Version (LeetCode 278)

   • Find first occurrence of condition

2. Search Insert Position (LeetCode 35)

   • Find insertion point (lower bound)

3. Find First and Last Position (LeetCode 34)

   • Lower and upper bound

4. Peak Index in Mountain Array (LeetCode 852)

   • Find peak element

5. Koko Eating Bananas (LeetCode 875)

   • Binary search on answer

6. Capacity To Ship Packages (LeetCode 1011)

   • Binary search on answer

7. Minimum Number of Days to Make m Bouquets (LeetCode 1482)

   • Binary search on answer

8. Find K Closest Elements (LeetCode 658)

   • Find window position

9. Split Array Largest Sum (LeetCode 410)

   • Binary search on answer

10. Median of Two Sorted Arrays (LeetCode 4)

    • Find partition point

Mixed (Can use either with adaptation)

1. Find Peak Element (LeetCode 162)

   • Pattern 1 or 2 depending on approach

2. Single Element in Sorted Array (LeetCode 540)

   • Pattern 1 or 2 works

---

Summary Cheat Sheet

// ============================================
// PATTERN 1: EXACT MATCH
// ============================================
function exactMatch(arr, target) {
    let left = 0;
    let right = arr.length - 1;  // INCLUSIVE
    
    while (left <= right) {      // <=
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] === target) return mid;  // Found
        
        if (arr[mid] < target) {
            left = mid + 1;      // Exclude mid
        } else {
            right = mid - 1;     // Exclude mid
        }
    }
    
    return -1;  // Not found
}

// ============================================
// PATTERN 2A: FIND BOUNDARY (exclusive right)
// ============================================
function findBoundary(arr, target) {
    let left = 0;
    let right = arr.length;      // EXCLUSIVE
    
    while (left < right) {       // <
        const mid = Math.floor(left + (right - left) / 2);
        
        if (condition) {
            left = mid + 1;      // Exclude mid
        } else {
            right = mid;         // Include mid
        }
    }
    
    return left;  // Converged position
}

// ============================================
// PATTERN 2B: FIND BOUNDARY (inclusive right)
// ============================================
function findBoundaryInclusive(arr, target) {
    let left = 0;
    let right = arr.length - 1;  // INCLUSIVE
    
    while (left < right) {       // <
        const mid = Math.floor(left + (right - left) / 2);
        
        if (condition) {
            left = mid + 1;      // Exclude mid
        } else {
            right = mid;         // Include mid
        }
    }
    
    return left;  // Converged position
}

Key Takeaways

1. Pattern 1 (left <= right): Use when finding exact elements

   • Right boundary: n - 1 (inclusive)
   • Both updates exclude mid: mid ± 1
   • Return -1 if not found

2. Pattern 2 (left < right): Use when finding positions/boundaries

   • Right boundary: n (exclusive) or n - 1 (inclusive)
   • One update keeps mid: right = mid
   • Return left (the converged position)

3. Consistency is key: Match your loop condition with your boundary updates

4. Always verify: Check edge cases and ensure your answer is valid before returning

Remember: The pattern you choose should match what you're looking for - an exact element or a boundary/position!