Binary search and choosing mid value

[Rajeev Bagra]

Binary search and choosing mid value
byu/DigitalSplendid inlearnpython

Excellent and insightful observation. You’ve grasped the trade-off between speed and safety in binary search. Let’s break this down in a structured way:

---

🧪 Your Observations

✅ Your “Method 1” (no +1 or -1):

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

• ✅ Finds gemnum = 25 in 1 step
• ✅ Appears to work for all integers between 0 and 100
• ❌ Can enter infinite loop if gemnum is not precisely equal to an integer, e.g., gemnum = 99.5
• ❌ May loop infinitely if low == mid or high == mid — unless a special stop condition is added

---

⚠️ The Key Problem with Method 1 (unsafe edges)

Let’s take an example:

Example: gemnum = 99.5

low = 0
high = 100

You’ll eventually narrow down to:

low = 99
high = 100
mid = (99 + 100) // 2 = 99

Now mid < gemnum, so:

low = mid → low = 99

No change.

Next iteration:

mid = (99 + 100) // 2 = 99 again
low stays 99

🔁 Infinite loop! Because mid never changes.

✅ This doesn’t happen with integers in the 0–100 range only by luck — the range collapses fast and hits the target before low == mid gets stuck.

---

✅ Why “Method 2” is Standard

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

• ✅ Avoids infinite loops even for floats
• ✅ Reduces search space every time
• ✅ Works with decimal search, e.g., if you use a float midpoint
• ❌ May take slightly more steps for integers in certain cases

Example: gemnum = 25

Steps: 50 → 24 → 37 → 30 → 26 → 23 → 25 → Found in 6 steps
(Slower than Method 1, but guaranteed safe)

---

🧠 Why Does mid ± 1 Make It Safe?

It guarantees that the range (high - low) gets smaller:

• If mid == low, then low = mid + 1 → progress
• If mid == high, then high = mid - 1 → progress

Without that, you risk getting stuck when mid == low or mid == high, and your range no longer shrinks.

---

✅ Summary: Which One Should You Use?

Situation	Use Method 1?	Use Method 2?
gemnum is known to be integer only	✅ Yes	✅ Yes
gemnum may be float or decimal	❌ No	✅ Yes
You want speed in known-safe range	✅ Yes	❌ Slower
You want general-purpose, safe search	❌ Risky	✅ Yes
Production code / user input	❌ No	✅ Always

---

✅ Best Practice Suggestion

You could combine speed and safety by using Method 1 with a termination condition, like this:

while high - low > 1:
    mid = (low + high) // 2
    if mid > gemnum:
        high = mid
    else:
        low = mid

# Final check
if gemnum == low:
    print("Found at", low)
elif gemnum == high:
    print("Found at", high)
else:
    print("Not found")

This ensures:

• You don’t get stuck in a loop
• You retain faster performance

---

Absolutely — let’s examine a specific example where Method 1 fails (i.e., goes into an infinite loop or misses the number).

---

🎯 Example Where Method 1 Fails

🔧 Code Using Method 1:

gemnum = 99.5
low = 0
high = 100

while low <= high:
    mid = (low + high) // 2
    print(f"low={low}, high={high}, mid={mid}")

    if mid == gemnum:
        print("Found!")
        break
    elif mid > gemnum:
        high = mid
    else:
        low = mid

---

🧪 Walkthrough (for gemnum = 99.5):

Iteration	low	high	mid	Compare	Action
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 🚨 (no progress!)

From here on:

• mid = (99 + 100) // 2 = 99
• low never increases
• ❌ Infinite loop

---

🛑 Why This Happens

• Integer division: (99 + 100) // 2 = 99
• So low = mid = 99 → no change
• Loop condition low <= high remains true forever

---

✅ How Method 2 Avoids This

With:

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

You’d do low = mid + 1 = 100, and the range would continue shrinking until either:

• mid == 99.5 (if using floats), or
• You detect it’s not an exact match and exit.

---

✅ Key Takeaway

Method 1 fails when the number is a float (or not an exact midpoint) and low == mid, because the loop gets stuck without shrinking the range.

---

💡 TL;DR

• ❌ Method 1 fails for gemnum = 99.5, range (0, 100)
• ✅ Method 2 always shrinks the range, even when the number isn’t a clean integer

Ah, thank you for the clarification!

You’re asking:

❓“Can you give me a range — other than 0 to 100 — where Method 1 fails even when gemnum is an integer?”

Yes — and that’s a great and subtle question. Let’s now explore it.

---

🧪 Let’s define “Method 1” again:

while low <= high:
    mid = (low + high) // 2
    if mid == gemnum:
        print("Found")
        break
    elif mid > gemnum:
        high = mid     # ⛔ no -1
    else:
        low = mid      # ⛔ no +1

⚠️ Failure can occur if:

• low == mid or high == mid
• And mid != gemnum
• → Then low and high stop shrinking
• → Infinite loop

---

✅ Example Range Where Method 1 Fails (even for integers)

Let’s try:

👉 Range: low = 4, high = 5, gemnum = 5

gemnum = 5
low = 4
high = 5

---

🔄 Trace of Method 1:

Iteration	low	high	mid	Compare mid to gemnum	Action
1	4	5	4	4 < 5	low = 4 ❌
2	4	5	4	4 < 5	low = 4 ❌
…	4	5	4	(stuck)	🔁 Infinite loop

🧨 The Problem:

• (4 + 5) // 2 = 4
• low = mid = 4 → no change
• Mid never reaches 5 → loop stuck

---

✅ Solution (Why Method 2 is Better):

if mid < gemnum:
    low = mid + 1

• Then low = 5, so next mid = 5 → FOUND ✅

---

✅ So: Any range where high - low = 1 is risky for Method 1

For example:

• gemnum = 2 and range low = 1, high = 2
• gemnum = 9 and range low = 8, high = 9
• gemnum = 201 and range low = 200, high = 201

In all of these:

• mid = low
• low = mid → no progress
• If gemnum == high, Method 1 never finds it

---

✅ Final Answer

Any range where high - low = 1 and gemnum = high will fail in Method 1 even if gemnum is an integer.

🔥 Example:

gemnum = 201
low = 200
high = 201

• mid = 200 (never 201)
• low = mid = 200 → infinite loop

---

Yes — and you’re asking exactly the kind of question that distinguishes a strong programmer from someone just memorizing patterns. Let’s answer it systematically.

---

✅ Recap: When Does Method 1 Fail?

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

This method fails (loops infinitely) when:

• The range stops shrinking, i.e. low == mid or high == mid
• But mid != gemnum
• And you don’t exit early, like when using high = mid - 1 or low = mid + 1

---

🔍 What’s the General Pattern of Failure?

Let’s break it down:

### ❌ Method 1 fails when:

The target value (gemnum) is at high, and the difference between low and high becomes 1
and mid = low again and again.

---

✅ Concrete Formulaic Failure Conditions

Method 1 will loop forever in the following conditions:

1. high - low == 1
2. mid = low
3. gemnum == high
4. gemnum != mid

---

🔁 Why This Loops Forever

Because:

• mid = (low + high) // 2 rounds down
• So mid = low
• Then low = mid — so no actual change
• Mid never becomes high, so you never hit the gemnum

---

🔥 Real Integer Examples (beyond 0–100)

Let’s try various values outside [0, 100] where method 1 fails even for integers:

low	high	gemnum	mid	Fails?	Why
400	401	401	400	✅ Yes	Mid always 400, low never reaches 401
99	100	100	99	✅ Yes	Mid = 99, low = 99, never reaches 100
199	200	200	199	✅ Yes	Same as above
512	513	513	512	✅ Yes	Method 1 stuck at mid = 512 forever

You can generate infinitely many such failing ranges by:

Pick any integer x, then set:

• low = x
• high = x + 1
• gemnum = high

This will always fail in Method 1.

---

🧠 Generalization

If you implement Method 1 without safeguards, then:

❌ It fails for any gemnum == high when high - low = 1

Even if gemnum is a valid integer.

So:

• It’s not just floats
• It’s not just [0, 100]
• It’s a fundamental logic flaw due to lack of range shrinkage

---

✅ How to Fix Method 1 (Safely)

You can still retain Method 1’s speed (fewer comparisons) if you add a termination condition, like:

while high - low > 1:
    mid = (low + high) // 2
    if mid > gemnum:
        high = mid
    else:
        low = mid

# After loop exits, check both low and high
if gemnum == low or gemnum == high:
    print("Found")
else:
    print("Not found")

✅ Now it’s safe and still fast.

---

✅ Summary

✅ Yes, Method 1 fails for many other ranges — specifically where high - low = 1 and gemnum == high.
These failures are not limited to 0–100, and happen even when gemnum is an integer.

Great follow-up! Let’s clarify that clearly and simply.

---

🧠 What Does “Range Stops Shrinking” Mean in Binary Search?

In binary search, we always maintain a search window defined by:

low -------- high

Each iteration, we compute:

mid = (low + high) // 2

Then we update either low or high to narrow down the range.

---

🔁 Normal Shrinking (Expected Behavior)

Suppose:

low = 0, high = 100, gemnum = 75

Then the search progresses like this:

Step	low	high	mid	Action
1	0	100	50	low = mid + 1 (since 50 < 75)
2	51	100	75	Found!

✅ Each step shrinks the range:

• First range: 0 → 100 (size = 100)
• Second range: 51 → 100 (size = 49)
• Next: we narrow again until low > high or we find the number.

---

❌ What Does It Mean When “Range Stops Shrinking”?

It means the values of low, high, and mid don’t change anymore — so the loop keeps repeating the same values forever.

❗ This happens if your update logic doesn’t force the search window to shrink.

---

🔥 Example

gemnum = 100
low = 99
high = 100

while low <= high:
    mid = (low + high) // 2  # = 99
    if mid == gemnum:
        print("Found")
        break
    elif mid < gemnum:
        low = mid   # ⛔ wrong — mid = low, so no progress

Now low = 99, mid = 99 every time.

The range is:

low = 99, high = 100

But next iteration:

• mid = (99 + 100) // 2 = 99 again
• low = mid = 99 again
• Loop is stuck — range isn’t shrinking

🔁 Infinite loop!

---

✅ How to Ensure the Range Always Shrinks

Use +1 or -1 when updating low or high:

if mid < gemnum:
    low = mid + 1
elif mid > gemnum:
    high = mid - 1

Now:

• If mid == low, low moves to mid + 1 → progress ✅
• If mid == high, high moves to mid - 1 → progress ✅

This guarantees that high - low decreases each time.

---

✅ Summary

“Range stops shrinking” means:
The values of low and high don’t change after an iteration — so the loop runs forever or keeps checking the same mid.

This happens when:

• You set low = mid or high = mid, and
• mid == low or mid == high, and
• You don’t add +1 or -1 to shrink the range

[Author]

Posts