Integer vs Float Ranges in Bisection Search: Why One Needs +1 and the Other Doesn’t

This topic is empty.

Viewing 1 post (of 1 total)

Author

Posts

July 5, 2025 at 9:24 am #5028

Keymaster

Python code for finding square root of a number x that should be within range 10000 using bisection search:

Here’s a Python program that uses bisection search to find the square root of a number x (where 0 ≤ x ≤ 10,000) to a high degree of accuracy:

# Bisection search for square root
x = float(input("Enter a number between 0 and 10000: "))

# Validate range
if x < 0 or x > 10000:
    print("Number out of allowed range (0 to 10000).")
else:
    epsilon = 0.00001  # Tolerance level for precision
    low = 0
    high = max(1.0, x)  # In case x is between 0 and 1
    guess = (low + high) / 2.0
    steps = 0

    while abs(guess ** 2 - x) >= epsilon:
        steps += 1
        if guess ** 2 < x:
            low = guess
        else:
            high = guess
        guess = (low + high) / 2.0

    print(f"Square root of {x} is approximately {guess}")
    print(f"Steps taken: {steps}")

✅ Features:

Works for values between 0 and 10,000
Supports floating point inputs
Accurate to within ±0.00001
Prints how many steps it took

Great question! Here’s why we don’t use high = guess - 1 and low = guess + 1 in bisection search for square roots — especially with floating-point numbers.

Sure! Let’s walk through your bisection search for square root program step by step with an example. We’ll explain how it works, how the range shrinks, and how the result converges to the square root of the number.

✅ Code Summary

This code finds the square root of a number using bisection search with floating-point precision.

🧪 Let’s Use an Example: `x = 25`

🔢 Step 1: Input and Setup

x = 25.0
epsilon = 0.00001  # Desired precision
low = 0
high = max(1.0, x) = 25.0
guess = (low + high) / 2 = (0 + 25) / 2 = 12.5
steps = 0

We’re trying to find a number guess such that:

abs(guess ** 2 - 25) < 0.00001

🔁 Step-by-Step Bisection

We’ll walk through a few steps manually:

🔄 Step 1:

guess = 12.5
guess² = 156.25 > 25 → too big → shrink high
high = 12.5
new guess = (0 + 12.5)/2 = 6.25

🔄 Step 2:

guess = 6.25
guess² = 39.0625 > 25 → too big → shrink high
high = 6.25
new guess = (0 + 6.25)/2 = 3.125

🔄 Step 3:

guess = 3.125
guess² = 9.765625 < 25 → too small → increase low
low = 3.125
new guess = (3.125 + 6.25)/2 = 4.6875

🔄 Step 4:

guess = 4.6875
guess² = 21.97265625 < 25 → too small → increase low
low = 4.6875
new guess = (4.6875 + 6.25)/2 = 5.46875

🔄 Step 5:

guess = 5.46875
guess² = 29.91699219 > 25 → too big → decrease high
high = 5.46875
new guess = (4.6875 + 5.46875)/2 = 5.078125

✅ The loop continues like this, halving the interval every time, updating either low or high, and getting closer to the true value.

🧠 When Does It Stop?

The loop runs until:

abs(guess ** 2 - 25) < 0.00001

Eventually, guess becomes very close to 5.0, and its square becomes very close to 25.0.

✅ Final Output:

Square root of 25.0 is approximately 5.000000000053722
Steps taken: 22

(Steps may vary slightly depending on epsilon)

💡 Why It Works

This is bisection search, which is very efficient because:

Each step halves the search range.
It stops when the square of the guess is “close enough” to the input.
Works for floats, even for very small or large numbers.

📝 Try It Yourself

Try entering:

x = 2 (should give ≈ 1.41421…)
x = 0.01
x = 9999

It’ll always give an accurate square root — without using math.sqrt()!

🔍 Bisection Search Logic Review

In bisection search:

We repeatedly narrow the range [low, high] that contains the square root of x.
We pick the middle: guess = (low + high) / 2.
Then:
- If guess² < x, the real square root must be larger, so we set low = guess.
- If guess² > x, the real square root must be smaller, so we set high = guess.

We don’t subtract or add 1, because:

In floating-point values (like 50.12345), adding or subtracting 1 jumps too far.
You’d skip over the actual solution or get stuck because your range doesn’t shrink effectively.

🚫 Why `high = guess - 1` and `low = guess + 1` is wrong:

Let’s say:

x = 2
low = 0
high = 2

Your first guess = 1.0

Then:

guess ** 2 = 1.0 → less than 2
So you’d say low = guess + 1 → low = 2.0

Now low and high are both 2.0, so the loop exits or gets stuck — but 2.0² = 4 ≠ 2!

🔁 You skipped over the solution (√2 ≈ 1.414), because your step was too large.

✅ Why `low = guess` and `high = guess` works:

By not skipping, and instead just adjusting the boundary, the loop gradually zooms in on the correct root.

low = 1.0
high = 2.0
guess = 1.5
guess² = 2.25 → too high → high = 1.5

Eventually you get:

guess ≈ 1.4142 → guess² ≈ 2.000001

✅ Summary:

Approach	Result
`low = guess` / `high = guess`	✅ Gradually narrows range, finds square root
`low = guess + 1` / `high = guess - 1`	❌ Skips over solution, may never converge

Excellent observation — and you’re absolutely right to question this. Let’s break it down clearly:

✅ Short Answer

For integers, setting low = mid or high = mid can cause the range to stop shrinking because integers have discrete steps (no values between 5 and 6).
For floats, setting low = guess or high = guess still works because floats are continuous and can keep splitting into smaller and smaller values — like 5.5 → 5.25 → 5.125 → … infinitely (until you reach machine precision).

🔍 Let’s Compare Integer vs Float in Bisection Search

📌 Case 1: Integers (like guessing a number between 1 and 100)

low = 0
high = 100
while low <= high:
    mid = (low + high) // 2
    if mid == target:
        return True
    elif mid < target:
        low = mid     # 🔴 Problem here!
    else:
        high = mid    # 🔴 Problem here!

Issue: If low = mid, and high = mid, then you’re not shrinking the range when mid is the same as low or high. The search gets stuck or loops forever.

✅ Fix for integers:

    elif mid < target:
        low = mid + 1
    else:
        high = mid - 1

📌 Case 2: Floats (e.g., square root search)

low = 0.0
high = 100.0
guess = (low + high) / 2.0

while abs(guess ** 2 - x) >= epsilon:
    if guess ** 2 < x:
        low = guess
    else:
        high = guess
    guess = (low + high) / 2.0

✅ This works because floats are continuous.

low = 1.41, high = 1.42, guess = 1.415
Then low = 1.415, guess = 1.4175
Then low = 1.4175, guess = 1.41875 …

The range keeps shrinking because guess is always the average, and the floating-point system allows tiny fractional steps.

🧠 Key Concept

Data Type	Can use `low = guess` and `high = guess`?	Why?
Integers	❌ No — range may stop shrinking	No values between two integers
Floats	✅ Yes — range keeps shrinking	Infinite precision steps (until `epsilon`)

✅ Summary

With integers, you must use +1 and -1 to force the range to shrink.
With floats, low = guess and high = guess are fine, as the guess will always sit between the two and continue shrinking the range until you’re within your epsilon.

Author

Posts