18 ms·
Binary search. Very simple, incredibly powerful; can search on data or math function. It's the basis for other CS concepts. JS implementation: https://gist.git
by netgusto 8y ago
Binary search. Very simple, incredibly powerful; can search on data or math function.
It's the basis for other CS concepts.
JS implementation: https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e14d00b https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e1...
- JonathanMerklin 8y agoIsn't this bit: const mid = Math.floor((right + left) / 2); susceptible to overflow? EDIT: Hm, perhaps not (in JS). Number.MAX_SAFE_INTEGER is much greater than I expected.
- josephg 8y agoNot in Javascript, where everything is a double precision float. You would lose precision at about 2^51, but that’s not a limit that will meaningfully affect us for good while.
- enedil 8y agoOh really? And what if you aren't storing the data? You just want to find such n, that f(n) >= m and f(n+1) < m. Now perhaps it might become an issue.
- netgusto 8y agoThank you, fixed it! const mid = Math.floor(left + (right - left) / 2); https://stackoverflow.com/q/27167943 https://stackoverflow.com/q/27167943
- deleted 8y ago[deleted]
- lou1306 8y agoIndeed, Java's binary search had this bug for a while! It was found through automatic verification, by the way. https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- agumonkey 8y agoalso some CS books
- FabHK 8y agoIncidentally, as outlined in this Julia FAQ, native machine arithmetic with overflow will deal with this correctly. mid = (lo + hi) >>> 1 https://docs.julialang.org/en/v1/manual/faq/index.html#Why-does-Julia-use-native-machine-integer-arithmetic?-1 https://docs.julialang.org/en/v1/manual/faq/index.html#Why-d... EDIT: legibility
- pimmen 8y agoI've used it as a very simple equation solver in a pinch. Yes, it's a very naive approach for most equations, but getting started solving it satisfactory with a solution given is very welcome.
- akhilcacharya 8y ago...wait, how? I’ve never heard of a use like this.
- lifthrasiir 8y agoIf f is monotonic and continuous, you can solve f(x) = y for x by successively narrowing an interval [a, b] where f(a) <= y <= f(b) (or vice versa for decreasing functions). In the case that the range of f spans the entire real numbers, the initial range can be determined as the smallest range [-2^k, 2^k] where k is an integer (a strategy often used for open-ended binary search).
- deleted 8y ago[deleted]
- jules 8y agoInterestingly, with floats you can also binary search on the binary representation. That narrows down the answer to the most precise answer representable in floating point in at most 64 steps for 64 bit floats. If you bisect the interval in the middle at each step, then it could take more steps (possibly more than 1000). It turns out that doing this is pretty much equivalent to what you suggest, if you narrow down the initial range [-2^k, 2^k] by binary searching on k, because that's just binary searching on the exponent in the binary representation.
- akhilcacharya 8y agoInteresting! I didn't really think about this but this is how I implemented sqrt() and division in an interview. Didn't think of how it generalizes!
- kmike84 8y agoRegarding "very simple" - as I recall from some book, first bug-free implementation appeared only after several years after invention / initial description of the algorithm. From wikipedia: "A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks" (https://en.wikipedia.org/wiki/Binary_search_algorithm https://en.wikipedia.org/wiki/Binary_search_algorithm).
- jules 8y agoI like this version: low = -1 high = arr.length while(high - low > 1){ mid = (high + low)/2 if(arr[mid] <= x) low = mid else high = mid } This eliminates all branches from the body of the loop (gets compiled to conditional move). It's also more general because it can be used to find the right position to insert a new element in a sorted array.
- karakot 8y agoand it's also a broken version.
- jules 8y agoHow so? Are you talking about (high + low)/2? Whether that is correct depends on the language. With 64 bit arithmetic it's correct in practice, and with arbitrary size arithmetic it's correct in practice and in theory. It only really causes problems if you're using 32 bit arithmetic on a 64 bit machine.
- ncmncm 8y agoJust keep telling yourself that. Or, look up the right answer.
- jules 8y agoPerhaps instead of being mean, you could be helpful and post a link to said answer.
- raymond_goo 8y agoWith 64 bit variables it probably works. But for less here is the correct implementation: https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- 8y ago
- gyrgtyn 8y agoA cool thing about binary search is you can also use it in real life. It's great for troubleshooting.
- api_or_ipa 8y ago`git bisect` is an indispensible git trick. You give it commit where you know the bug exists, and one where you know it doesn't and it'll use binary search to help you find where the bug came from. It's absolutely wonderful.
- HereBeBeasties 8y agoI always struggle to see why people bang on about git bisect. You need tests to make it work. If you have tests, why aren't you running them continuously? If you're running them continuously, why do you need git bisect?
- BenjiWiebe 8y agoBecause your tests didn't have 100% coverage.
- Narretz 8y agoIf the bug is a regression, you write the test after finding it, and execute it with git-bisect. If the test starts to pass, you have the commit where it will fail.
- HereBeBeasties 8y agoIf I can write a failing test, I can likely fix it. If I am interested in seeing who broke it and when, I can run git blame on the thing I'm fixing. Given that my test suite is generally in the same repo as the code, I'd need to write something that patched my new test into the codebase at every git bisect commit, recompile and run it. I can see that this may occasionally be useful if you have an extremely hard to find bug, but for me it's pretty rare. In fact I've done this once, ever. Hence my skepticism when people describe this as "git's killer feature" or whatever other hyperbole.
- doomjunky 8y agoHave a look at interpolation search. The complexity is O(log log n), under the assumption of a uniform distribution of the data. https://en.wikipedia.org/wiki/Interpolation_search https://en.wikipedia.org/wiki/Interpolation_search