AI, Data Science, & Programming for Small Business Applications & Large Enterprises › Forums › CS50’s Introduction to Computer Science by Harvard University on Edx › Week 6: Python › MITx 6.100L Introduction to CS and Programming Using Python › Binary search and choosing mid value
- This topic is empty.
-
AuthorPosts
-
July 5, 2025 at 4:19 am #5025
Binary search and choosing mid value
byu/DigitalSplendid inlearnpythonExcellent 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
orhigh == 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
, thenlow = mid + 1
→ progress - If
mid == high
, thenhigh = mid - 1
→ progress
Without that, you risk getting stuck when
mid == low
ormid == 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
orhigh == mid
- And
mid != gemnum
- → Then
low
andhigh
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
togemnum
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 nextmid = 5
→ FOUND ✅
✅ So: Any range where
high - low = 1
is risky for Method 1For example:
gemnum = 2
and rangelow = 1
,high = 2
gemnum = 9
and rangelow = 8
,high = 9
gemnum = 201
and rangelow = 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
andgemnum = high
will fail in Method 1 even ifgemnum
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
orhigh == mid
- But
mid != gemnum
- And you don’t exit early, like when using
high = mid - 1
orlow = mid + 1
🔍 What’s the General Pattern of Failure?
Let’s break it down:
### ❌ Method 1 fails when:
The target value (
gemnum
) is athigh
, and the difference betweenlow
andhigh
becomes 1
andmid = low
again and again.
✅ Concrete Formulaic Failure Conditions
Method 1 will loop forever in the following conditions:
high - low == 1
mid = low
gemnum == high
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 100199 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
whenhigh - 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
andgemnum == 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
orhigh
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
, andmid
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
againlow = mid = 99
again- Loop is stuck — range isn’t shrinking
🔁 Infinite loop!
✅ How to Ensure the Range Always Shrinks
Use
+1
or-1
when updatinglow
orhigh
:if mid < gemnum: low = mid + 1 elif mid > gemnum: high = mid - 1
Now:
- If
mid == low
,low
moves tomid + 1
→ progress ✅ - If
mid == high
,high
moves tomid - 1
→ progress ✅
This guarantees that
high - low
decreases each time.
✅ Summary
“Range stops shrinking” means:
The values oflow
andhigh
don’t change after an iteration — so the loop runs forever or keeps checking the samemid
.This happens when:
- You set
low = mid
orhigh = mid
, and mid == low
ormid == high
, and- You don’t add
+1
or-1
to shrink the range
- ✅ Finds
-
AuthorPosts
- You must be logged in to reply to this topic.