Binary-like search

user_12211073 0
Viewed 83

It's theoretical question.

exercise from leetcode as basis.

My solution for task is binary search. But question is not about it.

I found perfect solution on Discuss tab.

(next code has been taken from there)

class Solution:
    def mySqrt(self, x: int) -> int:
        low, high= 1, x
        while low<high:
            high = (low + high) // 2
            low = x // high

        return high

It works perfect. My question is:

For regular binary search we take middle of sequence and depending of comparison result remove excessive part (left or right) next repeat till result.

What is this implementation based on?

This solution cut part of sequence right after middle and small part from start.

search algorithm python
2 Answers

This code isn't based on binary search. It's based instead on adapting the ancient "Babylonian method" to integer arithmetic. That in turn can be viewed as anticipating an instance of Newton's more-general method for finding a root of an equation.

Keeping distinct low and high variables isn't important in this code. For example, it's more commonly coded along these lines:

def intsqrt(n):
    guess = n  # must be >= true floor(sqrt(n))
    while True:
        newguess = (guess + (n // guess)) // 2
        if guess <= newguess:
            return guess
        guess = newguess

but with more care taken to find a better initial guess.

BTW, binary search increases the number of "good bits" by 1 per iteration. This method approximately doubles the number of "good bits" per iteration, so is much more efficient the closer the guess gets to the final result.

user_27055420

This method is subtle, though was known of the Babylonians (see Tim's answer).

Assume that h > √x. Then

  1. l = x/h < √x and
  2. (l+h)/2 > √x.

The first property is obvious. For the second, observe that 1. and 2. imply x+h² > 2h√x or (h-√x)^2 > 0, which is true.

So h remains above √x, but it gets closer and closer (because (l+h)/2 < h). And when the computation is made with integers, there is a moment such that l≥h.

How was this method discovered ?

Assume that you have an approximation h of √x and we want to improve it, with a correction δ. We write x = (h-δ)² = h²-2hδ + δ² = x. If we neglect δ², then we draw h-δ = (h²+x)/2h = (h+x/h)/2, which is our (h+l)/2.

user_11965490
Related