Demystifying Binary Search Ranges: Inclusive vs Exclusive

Binary search is a staple algorithm in every coder’s toolbox. Yet, a subtle confusion haunts many developers: Should I use inclusive (start <= end) or exclusive (start < end) bounds?

Let’s break it down with clear examples and real reasoning so you never second-guess again.

---

🤯 The Root of the Confusion

Most tutorials teach binary search using inclusive bounds:

int start = 0, end = n - 1;
while (start <= end) {
    int mid = (start + end) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) start = mid + 1;
    else end = mid - 1;
}

This works perfectly for exact element searches, but gets tricky when we move to boundary problems like finding the lower bound or upper bound.

---

🔍 Boundary Problems? Like what?

• Lower Bound: First index where arr[i] >= target

• Upper Bound: First index where arr[i] > target

In these cases, you’re not looking for equality—you’re looking for a position. And this is where exclusive bounds shine.

---

✅ Exclusive Range for Boundaries

int lowerBound(int[] arr, int target) {
    int start = 0, end = arr.length;
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return start; // start == end at the end
}

Why is this better?

• 🔁 Loop always terminates at the exact position.

• 🧠 No extra variable to track the answer.

• 🔄 Easy to generalize for both lower and upper bound.

• 🔍 Works even when the target is larger than all elements or smaller than all.

Example:

For arr = [1, 2, 4, 4, 5] and target = 4, lowerBound returns 2 (first index of 4). For target = 3, it returns 2 (position to insert 3).

---

🆗 Inclusive Range Works Too, But...

int lowerBound(int[] arr, int target) {
    int start = 0, end = arr.length - 1;
    int ans = arr.length;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] >= target) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return ans;
}

• 🧮 You must manage an extra ans variable.

• 🧱 More edge cases due to end = arr.length - 1.

• 🪤 More prone to off-by-one errors.

Example:

Same arr = [1, 2, 4, 4, 5], target = 4:

• You set ans = 5 initially.

• When you find 4 at index 2, ans is updated.

• Loop ensures smallest index where arr[i] >= target is found.

---

⚖️ Inclusive vs Exclusive: When to Use What?

---

💡 Pro Tip

Use inclusive (<=) for exact searches and exclusive (<) for boundaries (lower bound / upper bound). It keeps your logic simpler and your bugs fewer.

---

🧠 Final Thought

You can use either form if you’re careful—but choose the right tool for the job. If you’re explaining this to juniors or writing interviews, stick with exclusive for boundaries.

Let the bugs fear you—not the other way around.