Binary Search in Python: Integer Square Root

In this video, we will be writing a function that computes the integer square root of a given number as input without using any built-in square root function.

Specifically, write a function that takes a non-negative integer and returns the largest integer whose square is less than or equal to
the integer given:

Example:

Assume input is integer 300.

Then the expected output of the function should be 17 since 17 squared is 289 which is strictly less than 300. Note that 18 squared is 324 which is strictly greater than 300, so the number 17 is the correct response.

This video is one part of the Binary Search playlist on my channel. For more videos on binary search and how to apply it to various problems, check out the other videos:

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[ramfattah]

this guy really deserves over 10 millions subscribers!!!! great content for anyone who is trying to get a job as a software engineer.

[shonnoronha]

Awesome series! Looking forward for new videos

[mightyprogrammer]

am little bit confused in (return low - 1)
why
why not (return mid - 1)
by the way explanation was so good :)

[SomeOfOthers]

3:06 "It's OK (O(k)) this will work...."
intentional pun? haha

[arnoldn]

Why not start the low value at 2^(log2(k)-1) (shift k right over half the number bits of k itself)

[ThatInsaneGuy]

Cant we just use this method. It will save a lot of space and time.

def integerSquareRoot(number):
return int(number ** 0.5)

print(integerSquareRoot(20))


print(integerSquareRoot(16))


ANS -
4
17
31
4

[adirbarak]

I like the idea of this series and I know you got to be creative making all these scenarios but in this case the answer is always k**0.5 // 1 (or int(k**0.5))
* it is because k is int and > 0, the biggest int to come close or equal is the closest int to its root (its own root if it is int or the floor division of its root)
it's nice to implement binary search to find it but its just a very long and ineffective way in this specific example
tl:dr you can use binary search for fun or novelty but its really unreasonable.

[winterheat]

it is quite tricky to write correctly... especially on the whiteboard and no computer

[alexkhalamsky]

Why cant i just take the square root and round it to the floor?