Why You Must Use +1 and -1 in Bisection Search: A Deep Dive with Examples

Bisection search: Reason for subtracting 1 in case of high and adding 1 in case of low with firstnum
byu/DigitalSplendid inlearnpython

---

Bisection search — is one of the most efficient ways to find a value in a sorted list or range. It’s a classic divide-and-conquer algorithm that cuts the search space in half each time, giving it a powerful time complexity of O(log n).

But there’s a subtle trap many beginners fall into:

❗ Not excluding the midpoint (mid) from the next search interval.

In this post, we’ll explore why it’s critical to adjust the bounds properly using +1 and -1, and what can go wrong if you don’t — including infinite loops, stuck iterations, and never terminating when the target isn’t found.

---

⚙️ The Structure of Bisection Search

Here’s how a correct bisection search typically works:

low = 0
high = len(arr) - 1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        high = mid - 1  # ⬅️ eliminate mid
    else:
        low = mid + 1   # ⬅️ eliminate mid

The mid - 1 and mid + 1 parts are essential. They exclude the current mid value from the next search range, because we’ve already checked it.

---

🤔 What Happens If You Don’t Use +1 or -1?

Let’s say you do this instead:

if arr[mid] > target:
    high = mid   # ❌ wrong
else:
    low = mid    # ❌ wrong

You haven’t excluded mid. That might seem harmless — but in practice, it breaks the whole algorithm.

---

🔁 Example 1: Target Not Present — Infinite Loop

Let’s search for target = 99.5 in a list of integers from 0 to 100. This number doesn’t exist in the list.

low = 0
high = 100

while low <= high:
    mid = (low + high) // 2
    if mid > 99.5:
        high = mid    # ❌ wrong
    else:
        low = mid     # ❌ wrong

Step-by-step:

• mid = 50 → too low → low = 50
• mid = 75 → too low → low = 75
• …
• mid = 99 → too low → low = 99
• mid = 99 → too low → low = 99
• mid = 99 → again!

🔁 You’re stuck infinitely checking mid = 99.

You’ve stopped shrinking the search space — that’s the problem!

---

🔁 Example 2: Target Is Present — Still Stuck

Now let’s say the target is 99 (which is in the list), but you still don’t use +1 or -1.

if mid > target:
    high = mid   # ❌
else:
    low = mid    # ❌

Eventually you’ll get:

• mid = 99 → matches target → great!
• But if you mistakenly check arr[mid] != target, or need more precision (e.g., float comparison), you could:
• loop forever
• never reach the exact value

Without +1 and -1, you may keep checking the same value again and again, and never converge.

---

✅ The Fix: Always Exclude mid

To prevent this, the correct binary search approach must adjust the bounds like this:

if mid > target:
    high = mid - 1  # Exclude mid
elif mid < target:
    low = mid + 1   # Exclude mid
else:
    return mid      # Found it

Each iteration now guarantees that the search range shrinks. Eventually, either:

• You find the target, or
• low > high, and you exit the loop correctly.

---

📊 Visual Summary

Incorrect Way	Correct Way
high = mid	high = mid - 1
low = mid	low = mid + 1
Might recheck same value	Always excludes mid
Can get stuck forever	Always progresses

---

🧠 Pro Tip: Bisection Search is Precise, But Sensitive

Bisection search is powerful, but it’s also sensitive to off-by-one errors. Always make sure you:

• Exclude the mid after using it.
• Use // 2 for integer division in Python.
• Handle edge cases where the target doesn’t exist.

---

🧪 Final Thoughts

The devil is in the details. Bisection search isn’t just about halving the list — it’s about doing it right.

Next time your bisection search is stuck in an infinite loop or not returning results, remember:

Did I exclude the midpoint properly using +1 or -1?

That one line could be the difference between an elegant solution and a frustrating bug.

---

---