Part of course:

Binary search extended

- Example

NaN.

Part of course: Competitive Programming: From Beginner to Expert

Binary search extended[ Edit ]

which associates integers (indices) with the corresponding values. However, there is no reason to restrict our usage of binary search toA sequence (array) is really just a functionsequences. In fact, we can use the same algorithm described above ontangible... The only difference is that we replace an array lookup with a function evaluation: we are now looking for some x such that f(x) is equal to the target value.any monotonic function f.

Source: TopCoder

__Problem__: Given a perfect square S (such as 16129 = 127 * 127) between 1 and 10 ** 6, find its square root (assuming you don't know how to calculate the square root).

__Solution__: Since the square is between 1 and 10 ** 6, we know that the square root must lie between 1 and 1000. We can keep halving this interval by taking the middle integer M in that range, and comparing M*M with S. For example, in the first step M = 500, and 500 * 500 > 16129, so the new range is 1 to 500. **Note that we don't need to compute the squares of all the numbers between 1 and 1000**.

Check out the TopCoder tutorial if you want a lengthier more detailed explanation. The magic starts in section "Beyond arrays: the discrete binary search".

To discuss this topic, check out the posts. And as always, feel free to ask questions!

Read more…(239 words)

Mark as completed

Previous

Binary search: Video tutorial, Python code and extensions

Next

[SPOJ AGGRCOW] Aggressive cows!

Part of courses:

About the contributor:

Keshav DhandhaniaIOI medalist. DM me for 1-on-1 mentorship (paid).

100%

Loading…

Have a question? Ask here…

Post

Part of course:

Binary search extended

- Example

Ready to join our community?

Sign up below to automatically get notified of new courses, get **reminders** to finish ones you subscribe to, and **bookmark** lessons to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.

Popular Courses

New Courses

About Us

Get in touch

Copyright 2016-18, Compose Labs Inc. All rights reserved.