FutureMind Academy

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