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

[Rajeev Bagra]

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

Great question! You’re trying to understand this key part of bisection (binary) search:

elif firstnum > gemnum:
    high = firstnum - 1
else:
    low = firstnum + 1

Let’s walk through why we subtract 1 or add 1 to narrow the search range properly.

---

🎯 The Goal of Bisection Search

You’re looking for a target value (gemnum) in a sorted range.

Each time, you check the middle number (firstnum = (low + high) // 2), and based on the result:

• If it’s too high → eliminate the right half
• If it’s too low → eliminate the left half

---

🔍 Why high = firstnum - 1

• When firstnum > gemnum, it means the number we want is strictly less than firstnum.
• So we eliminate firstnum itself and everything above it.
• That’s why we set the new upper bound (high) to firstnum - 1.

🧠 Example:

Suppose gemnum = 30

• low = 0, high = 100 → firstnum = 50
• 50 > 30 → we know gemnum is somewhere between 0 and 49
• So we set: high = 50 - 1 = 49

---

🔍 Why low = firstnum + 1

• When firstnum < gemnum, it means the number we want is strictly greater than firstnum.
• So we eliminate firstnum itself and everything below it.
• That’s why we set the new lower bound (low) to firstnum + 1.

🧠 Example:

Suppose gemnum = 70

• low = 0, high = 100 → firstnum = 50
• 50 < 70 → gemnum must be between 51 and 100
• So we set: low = 50 + 1 = 51

---

🧩 Why Not Just Set high = firstnum or low = firstnum?

If you do not exclude firstnum (by subtracting or adding 1), your loop might:

• get stuck checking the same number over and over
• never terminate, especially if gemnum isn’t in the list/range

Using -1 and +1 guarantees that you shrink the search space each time and avoid infinite loops.

---

✅ Final Summary:

Condition	What It Means	What to Do	Why?
firstnum > gemnum	Guess too high	high = firstnum - 1	Eliminate firstnum and everything above it
firstnum < gemnum	Guess too low	low = firstnum + 1	Eliminate firstnum and everything below it
firstnum == gemnum	Correct guess	break	Found it!

---

Absolutely — let’s explore this more deeply with a concrete example, to show why using high = firstnum or low = firstnum (without -1 or +1) can break the algorithm.

---

❗ The Core Problem: Infinite Loop or Stagnation

If you don’t update your bounds strictly (by adding or subtracting 1), you may not reduce the search range. This can lead to the loop checking the same firstnum repeatedly, resulting in:

• an infinite loop if the target isn’t found
• a stuck search that never converges

---

📌 Example: Target not present (e.g., gemnum = 99.5)

Let’s pretend the list or range only includes integers from low = 0 to high = 100.

You’re searching for gemnum = 99.5 (not actually in the range), and you’re using this wrong logic:

if firstnum > gemnum:
    high = firstnum   # ❌ no -1
else:
    low = firstnum    # ❌ no +1

Let’s walk through:

---

❌ Faulty Version (no -1/+1)

Initial range: low = 0, high = 100

1. firstnum = (0 + 100) // 2 = 50 → 50 < 99.5
   → low = 50
2. firstnum = (50 + 100) // 2 = 75 → 75 < 99.5
   → low = 75
3. firstnum = (75 + 100) // 2 = 87 → 87 < 99.5
   → low = 87
4. firstnum = (87 + 100) // 2 = 93 → 93 < 99.5
   → low = 93
5. firstnum = (93 + 100) // 2 = 96 → 96 < 99.5
   → low = 96
6. firstnum = (96 + 100) // 2 = 98 → 98 < 99.5
   → low = 98
7. firstnum = (98 + 100) // 2 = 99 → 99 < 99.5
   → low = 99
8. firstnum = (99 + 100) // 2 = 99 again
   → low = 99 (no change!)
9. Infinite loop: firstnum will keep returning 99 forever!

---

✅ Correct Version (with +1 / -1)

if firstnum > gemnum:
    high = firstnum - 1
else:
    low = firstnum + 1

Let’s see what happens now:

Initial range: low = 0, high = 100

1. firstnum = 50 → 50 < 99.5 → low = 51
2. firstnum = 75 → 75 < 99.5 → low = 76
3. firstnum = 88 → low = 89
4. firstnum = 94 → low = 95
5. firstnum = 97 → low = 98
6. firstnum = 99 → low = 100
7. firstnum = 100 → 100 > 99.5 → high = 99

✅ Now: low = 100, high = 99 → loop exits.
We correctly detect that 99.5 isn’t found in the integer list.

---

💡 Summary: Why -1 and +1 Are Necessary

Without -1/+1	With -1/+1
May recheck same firstnum	Always narrows search range
Can cause infinite loops	Always converges or exits
Range doesn’t shrink	Range shrinks every loop

---

🧠 Rule of Thumb:

• When you eliminate a half, you must fully exclude the midpoint (firstnum) that’s already been tested.
• Otherwise, your search space never shrinks — and that’s fatal in divide and conquer.

---

Great! Let me walk you through a diagram-based explanation to visually show how binary search works with and without the +1 / -1 bounds adjustment.

---

🔍 Scenario: We’re searching for gemnum = 99.5

• Our list (or range) has integers only, from 0 to 100
• gemnum = 99.5 is not in the list
• Let’s compare two strategies:

---

❌ Wrong Method – No +1 or -1

if firstnum > gemnum:
    high = firstnum
else:
    low = firstnum

Step	low	high	firstnum = (low+high)//2	Comparison	Updated Range
1	0	100	50	50 < 99.5 → go up	low = 50
2	50	100	75	75 < 99.5	low = 75
3	75	100	87	87 < 99.5	low = 87
4	87	100	93	93 < 99.5	low = 93
5	93	100	96	96 < 99.5	low = 96
6	96	100	98	98 < 99.5	low = 98
7	98	100	99	99 < 99.5	low = 99
8	99	100	99	99 < 99.5	low = 99 again
9	99	100	99	99 < 99.5	low = 99 again

🔁 This loop gets stuck! firstnum = 99 forever.
❗ The range doesn’t shrink — infinite loop.

---

✅ Correct Method – With +1 / -1

if firstnum > gemnum:
    high = firstnum - 1
else:
    low = firstnum + 1

Step	low	high	firstnum	Comparison	Updated Range
1	0	100	50	50 < 99.5	low = 51
2	51	100	75	75 < 99.5	low = 76
3	76	100	88	88 < 99.5	low = 89
4	89	100	94	94 < 99.5	low = 95
5	95	100	97	97 < 99.5	low = 98
6	98	100	99	99 < 99.5	low = 100
7	100	100	100	100 > 99.5	high = 99

💥 low = 100, high = 99 → condition low <= high fails
✅ Loop exits: target not found

---

🎯 Visualization Summary:

Wrong version:
   [ stuck at 99 ]
    low: 99
   high: 100
   mid:  99  ← stuck here forever!

Correct version:
   [ 98 ] → 99 → 100 → exit
   low: grows
   high: shrinks

---

🧠 Key Rule:

Always eliminate the middle value after checking it.

• high = mid - 1 if too high
• low = mid + 1 if too low

That guarantees:
✅ You never recheck the same value
✅ The range shrinks every loop
✅ You either find the value or exit cleanly

---

Excellent — let’s now dive deeply with examples to show what happens if you don’t use high = mid - 1 or low = mid + 1 in binary search, and instead do:

high = mid
low = mid

This logic fails because it doesn’t exclude the midpoint (mid) — which leads to:

• infinite loops
• repeated guesses
• never narrowing the search range

---

🔁 Example 1: Target not present in the list (e.g., gemnum = 99.5)

Let’s search in this range:

low = 0
high = 100
gemnum = 99.5  # Not an integer; not in the list

Let’s simulate wrong code:

if mid > gemnum:
    high = mid     # ❌ wrong — should be mid - 1
else:
    low = mid      # ❌ wrong — should be mid + 1

---

Step-by-step simulation:

Step	low	high	mid = (low + high)//2	Comparison	Updated Range
1	0	100	50	50 < 99.5	low = 50
2	50	100	75	75 < 99.5	low = 75
3	75	100	87	87 < 99.5	low = 87
4	87	100	93	93 < 99.5	low = 93
5	93	100	96	96 < 99.5	low = 96
6	96	100	98	98 < 99.5	low = 98
7	98	100	99	99 < 99.5	low = 99
8	99	100	99	99 < 99.5	low = 99
9	99	100	99	99 < 99.5	still 99
🔁	…	…	99	loop forever	no progress

💥 It’s stuck checking mid = 99 forever — infinite loop!

---

💡 Why This Happens

When you do:

low = mid  # or high = mid

You’re keeping the same midpoint in the next iteration, unless the range changes. So mid gets calculated as the same value again and again.

---

🛠️ Fix It with +1 and -1

Let’s use the correct binary search update:

if mid > gemnum:
    high = mid - 1
else:
    low = mid + 1

Same example, now correctly:

Step	low	high	mid	Action
1	0	100	50	low = 51
2	51	100	75	low = 76
3	76	100	88	low = 89
4	89	100	94	low = 95
5	95	100	97	low = 98
6	98	100	99	low = 100
7	100	100	100	high = 99
❌	low > high	Loop ends correctly

✅ Result: we cleanly exit, knowing the number is not in the list.

---

🔁 Example 2: Target is present in the list

Suppose we search for gemnum = 99, and again mistakenly do:

if mid > gemnum:
    high = mid
else:
    low = mid

Here’s what happens:

Step	low	high	mid	Outcome
1	0	100	50	low = 50
2	50	100	75	low = 75
3	75	100	87	low = 87
4	87	100	93	low = 93
5	93	100	96	low = 96
6	96	100	98	low = 98
7	98	100	99	low = 99
8	99	100	99	low = 99 again!
🔁	…	…	99	Infinite loop

🔁 You never actually “accept” the correct guess, because you’re not shrinking the search space.

---

✅ Takeaway:

Binary search works ONLY if you eliminate the current mid from future consideration:

# Correct pattern
if mid > target:
    high = mid - 1
elif mid < target:
    low = mid + 1
else:
    found it

Otherwise, your range never shrinks, and the loop never ends — especially when:

• the value isn’t in the list
• or the midpoint repeats without exclusion

---

[Author]

Posts