#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/binary-search-on-real-numbers

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/binary-search-on-real-numbers

Repovive

Binary Search on Real Numbers - Binary Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Binary Search on Real Numbers

When the answer is a floating-point value.

Binary search on reals uses precision threshold or fixed iterations.

Example: $\sqrt{x}$

function sqrt(x):
    lo = 0, hi = max(1, x)
    for i from 1 to 100:
        mid = (lo + hi) / 2
        if mid * mid < x: lo = mid
        else: hi = mid
    return lo

Why $100$ iterations? Each halves error. After $100$ : error $< (hi-lo)/2^{100}$ , negligible.

Alternative: while hi - lo > 1e-9. Careful with floating-point comparison.