News for hackers. Stuff that matters.
Re:On Binary Search by MauranKilom on Wednesday October 30, 2019 @07:35PM (#21404177)
Is this machine-generated text? That or it's badly translated. Either way, it's strangely incoherent and subtly flawed.

Take just the first section. It talks about a bubble sort of ints. Then provides code for bubble sorting strings [1]. Then talks about "sign position in the ASCII table". "linking to the native sort function" is... not the right term (what happened to "call"?). And then we suddenly talk about "the element to be found" (weren't we just sorting?). The rest of the article is in the same vein.

I hope I'm not coming across as just picking on someone's English skills - even with perfect English I would find it hard to follow the train of thought.

[1] This is subtly different because (naive) string comparison is not constant-time, unlike comparing ints in most languages. I was half expecting the article to go there but it didn't.

PS: If not for the discussion here, I would've skipped the read because the site has no HTTPS. Please get a cert, it's free: https://letsencrypt.org/

Re:On Binary Search by claes-magnus on Thursday October 31, 2019 @03:36AM (#21406460)
@Mauran Kilom. Thank you for your criticism, especially your mention of https://letsencrypt.org/. I will look into that! And I am also very grateful that your pointed out the obvious: the red thread was missing, and I have tried to fix this by erasing large parts of the text. My english is however as it is, much to improve! :) Thank your the time!
Re:On Binary Search by idbfs on Wednesday October 30, 2019 @07:48PM (#21404278)
I was wondering the same thing. It's either a horrible human-written article, or an impressive machine-written one.
Re:On Binary Search by gigatexal on Thursday October 31, 2019 @07:17AM (#21407522)
It could be a non-native speaker of English trying his or her best.
Re:On Binary Search by adrianmonk on Wednesday October 30, 2019 @06:38PM (#21403678)
> The problem with linearity is that the time to return the correct position grows exponentiality with the size of the dataset and of the position of the value to be found

No, the time required for linear search does not grow exponentially. It doesn't even grow quadratically. It grows linearly.

Re:On Binary Search by tempguy9999 on Wednesday October 30, 2019 @06:53PM (#21403829)
Agreed. It's such a strange statement I suspect he meant something else but I can't see what.
Re:On Binary Search by akamoonknight on Wednesday October 30, 2019 @07:30PM (#21404154)
Could they have meant exponentially with respect to using binary search? That is, using linear search is exponentially worse than using binary search on a sorted data set.
Re:On Binary Search by adrianmonk on Wednesday October 30, 2019 @10:36PM (#21405219)
That's an interesting theory. It is indeed exponentially worse then. Binary search is O(log N), and linear search is O(N).

If you let M=log N, then binary search is O(M) and linear search is O(e^(log N)) = O(e^M). So viewed that way, it's O(M) vs. O(e^M), an exponential relationship.

But the blog would still not be 100% right because it adds a qualifier. It says "grows exponentiality with the size of the dataset".

Re:On Binary Search by claes-magnus on Thursday October 31, 2019 @01:31PM (#21411376)
I want to try attempt explaining what I meant. @adriamonk: if you have the time, feel free to help me out here. :)

First, my point relates to JavaScript.

``` Take this code: const list = [2,1,2,"4", 5]; console.log( list.sort((a,b) => a-b) ); // [1, 2, 2, "4", 5] ``` This is kind of correct (or wrong), depending on how to view things. But I think we must acknowledge this as a part of the language design of JavaScript.

However, using strict eq... ``` console.log( list.findIndex((value) => value === 4) ); // -1 ``` Correct, sure.

On the other hand... ``` console.log( list.findIndex((value) => value == 4) ); // 3 ``` But now we're using a non strict form of equality.

In JavaScript, the aspects of the language described above can cause a problem concerning binary search. Because of JSs lack of strictness, we can't trust our data in the same way as in C or Rust or other languages (even though TypeScript could save us).

Sure if the preconditions aren't met, then we can't use BS. My point is that even though another language still would have to sort the elements in an array, we would know that all elements were of the same type in an array.

As programmers we want the behavior of our code to be predictable. And my point - I don't know if it is valid though - is that in JavaScript we can't. Therefore we would have to check every value in the array beforehand, and in JS we would have to do this linearly. I don't know if I misuse the terminology now, in that case, please tell me so (and I will be at least a bit wiser). My main point is that the big O of binary search is irrelevant in the context of JavaScript, if we're not 100% sure that our array is sorted and of the same type. Many other languages would have the first problem (we must trust the array to sorted), while JavaScript has to problems and this is more unpredictable. And I think we can only ensure this by the use of a linear method in JS.

Re:On Binary Search by Liquid_Fire on Thursday October 31, 2019 @07:30AM (#21407585)
Trivial nitpick: since this is binary search, the base for the logarithm is 2, not e. So it would be 2^M.
Re:On Binary Search by tempguy9999 on Thursday October 31, 2019 @08:01AM (#21407754)
Nitpick upon nitpick, the base may be 2 rather than e but IIRC the difference between lg(n) and log2(n) is a constant, and the log/lg term dominates, so it still is 0(log). I think.

Big fleas have little fleas upon their backs to bite 'em \ And little fleas have lesser fleas, and so, ad infinitum.

(https://en.wikipedia.org/wiki/The_Siphonaptera>

Re:On Binary Search by thethirdone on Thursday October 31, 2019 @08:45AM (#21408110)
Nitpick on Nitpick on Nitpick, it is indeed O(2^m) and not O(e^m). Those are not the same complexity.

Logs get to not care, but when we exponentiate it matters.

Re:On Binary Search by adrianmonk on Wednesday October 30, 2019 @07:18PM (#21404071)
I guess, informally, people sometimes say exponential when they just mean "way too much" or "extreme".

Someone might say, for example, "The party was already getting out of hand, but then my roommate's drinking buddies showed up and that's when things got exponentially worse."

Re:On Binary Search by claes-magnus on Wednesday October 30, 2019 @11:11PM (#21405399)
Thanks for comments! I will attempt to fix the flaws. Fixing the english will be harder though, for the time being my english is flawed (period). :)

I should provide some background. I don’t have any education in CS. This is an antempt on my behalf to fill gaps of knowledge. Being a junior frontend dev they are plenty, and I am thankful for your criticism (thanks again! You’ll make me better).

Anyway, I have changed the blog post! Mostly by erasing text. But if there are no good, clear red thread this is the best way. :) Thanks again!

Re:On Binary Search by kqr on Thursday October 31, 2019 @03:27AM (#21406421)
Thank you for exploring algorithmic concepts as a front-end developer! Keep that up and you'll get very far in your career.

I say this because we have interviewed nearly 150 front-end candidates and had to reject all but one due to their lack of very basic algorithm/data structure skills. I encourage anything that makes that pool less depressing!

Re:On Binary Search by claes-magnus on Thursday October 31, 2019 @04:11AM (#21406630)
I am not saying you are guilty of this, by I think this is sad in a way. My prejudice is that many frontend developers are interested in CS for the wrong reasons; I don't know if it's true though.

But CS as a career boost is very instrumental. I think it's better to focus on the good parts:

a) CS is fascinating, b) I also think there is an ethical side of CS. For each year, more 'logic' ends up in the frontend - I think. If this is true, there is an ethical dimension to it; not everyone have a new computer with the latest browser - performance has a ethical dimension.

Also, I for one hates when web sites are slow (so I guess there also is a business/economical side as well). But my main point is that - and no, I am not saying you're guilty of this, you clearly like CS (why comment otherwise), but the reasons you provide would gain from adding the perspective I am trying to provide, I think - is that CS should be studied because it is important, and fascinating. :)

I will never be good with CS. But if my own take on CS were only instrumental (career boost), I would most likely end up with less knowledge in comparison with reasons related to fascination (and ethics). I think this is an important point. Sure, it is perhaps made often. But in that case, I think it is important to repeat it. I see ads for many CS courses on i.e. Udemy with titles like CS for interviews and so on. I am not saying those course are bad (don't know); all I am saying is this is an instrumental view and that we (developers as a community) sometimes should be better at finding the right reasons.

Sorry, this was a long reply. :( :)

Re:On Binary Search by smellia on Thursday October 31, 2019 @02:14AM (#21406143)
Then you must have a look at the amazing elastic binary trees used in haproxy, the article describes their properties quite well in terms of binary search: https://wtarreau.blogspot.com/2011/12/elastic-binary-trees-e...

These were featured at QCon last June by one of their authors. Really great work.

Re:On Binary Search by claes-magnus on Thursday October 31, 2019 @03:26AM (#21406413)
@smellia: thank you very much for this suggestion! This seems really interesting. :)
Re:On Binary Search by carapace on Thursday October 31, 2019 @12:22PM (#21410457)
Keep up the good work! :-)
Re:On Binary Search by j-pb on Wednesday October 30, 2019 @06:16PM (#21403445)
Pretty blog, but though the title suggests some "insight" into binary search, there is not more than what would be taught in the first two weeks of an undergrad CS curriculum.
Re:On Binary Search by claes-magnus on Thursday October 31, 2019 @03:28AM (#21406425)
Thank you. CS is what I am trying to learn. :) I have not studied CS, only some vocational education in programming, and I am into front-end. However, I think this is important for someone like me, and it is really fascinating. :)
Re:On Binary Search by person_of_color on Wednesday October 30, 2019 @07:03PM (#21403929)
Good for interview prep, then!
Re:On Binary Search by devnonymous on Wednesday October 30, 2019 @06:39PM (#21403682)
Each time I see an implementation of binary search like this I can't help but recall:

https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

Which reminds me just how young the field of computer science is and how even the ^well known^, fundamental algorithms might have buggy implementations.

Re:On Binary Search by smitty1e on Wednesday October 30, 2019 @06:49PM (#21403794)
Working in IT affords occasion to be humble at least daily.
Re:On Binary Search by agentultra on Wednesday October 30, 2019 @07:08PM (#21403979)
A friend of mine did an experiment with his grad students in his Formal Methods class.

They all submitted their implementation of binary search and he modelled them each in TLA+. The majority of them all had errors.

Re:On Binary Search by person_of_color on Wednesday October 30, 2019 @07:07PM (#21403973)
Why does this implementation used signed integers for indices at all?
Re:On Binary Search by MauranKilom on Wednesday October 30, 2019 @07:21PM (#21404097)
Java. There are no unsigned integers in Java. Many would consider that a benefit (although opinions vary on signed vs unsigned bytes). FWIW, the creators of C++ have stated that they'd go with signed integers for e.g. indexes in the library interfaces nowadays (but it's way too late to change that).

Popular problem with using unsigned : Write a reverse for loop from n (exclusive) to 0 (inclusive). See if you can do it without discarding your two most intuitive (but wrong) approaches.

Re:On Binary Search by smellia on Thursday October 31, 2019 @02:19AM (#21406156)
Its the opposite. Its easy to write such a loop with unsigned ints: for(x=top;x<=top;x--). However you can't reliably write a loop spanning the whole space with signed ints without breaking the no-overflow rules. With unsigned you can do x=0;do{stuff(x);}while(++x); Good luck doing this with signed ints.
Re:On Binary Search by mypalmike on Thursday October 31, 2019 @10:07AM (#21408915)
This is why integer sign should be part of the operation rather than the type. Every language but assembly gets this wrong.
Re:On Binary Search by hansdieter1337 on Wednesday October 30, 2019 @07:07PM (#21403972)
"The problem with linearity is that the time to return the correct position grows exponentiality with the size of the dataset and of the position of the value to be found"

Eh...what? Linear = Exponential growth?

Re:On Binary Search by bla3 on Thursday October 31, 2019 @08:26AM (#21407945)
Your loop body looks incorrect. You're both adding 1 when updating low and subtracting 1 when updating high -- but you let the high index start at array.length. It's possible that your additional || clause before the high update mitigates the effects of this, but it's at best inefficient. To implement binary search effectively, it's useful to think about invariants. https://zhu45.org/posts/2018/Jan/12/how-to-write-binary-sear... looks like a decent post on this topic. Searching for "binary search loop invariant" or similar will find many similar articles. I recommend giving them a look, it's a useful thought framework for this algorithm :)
Re:On Binary Search by bla3 on Thursday October 31, 2019 @08:35AM (#21408023)
The highest-rated comment on https://stackoverflow.com/questions/504335/what-are-the-pitf... is also good.
Re:On Binary Search by claes-magnus on Thursday October 31, 2019 @09:16AM (#21408346)
Thank you!
Re:On Binary Search by RcouF1uZ4gsC on Wednesday October 30, 2019 @06:37PM (#21403672)
> The problem with linearity is that the time to return the correct position grows exponentiality with the size of the dataset and of the position of the value to be found;

I don't this is quite true.

Re:On Binary Search by xrisk on Thursday October 31, 2019 @09:34AM (#21408512)
This TopCoder article [1] on binary search is the most comprehensive one I've read on the topic so far. It covers the discrete and continuous variants and mentions some common pitfalls too.

[1]: https://www.topcoder.com/community/competitive-programming/t...

Re:On Binary Search by OrWestSide on Thursday October 31, 2019 @11:57AM (#21410147)
Just read your article. Something about the way you write made me look at your archives. Now I am coding a maze generator using prim's algorithm. For fun.

Yes, you should get a certificate for your site, yes there is room for improvement for your english and yes you have a long long way to go to just get a grasp of CS fundamentals.

But don't stop trying man. You just inspired me :)

Re:On Binary Search by claes-magnus on Thursday October 31, 2019 @01:13PM (#21411142)
Great! That’s why we have communities such as this one?! :) To inspire each other; even when we are wrong... Curiosity is contagious, I guess. :)
Re:On Binary Search by userbinator on Thursday October 31, 2019 @07:48AM (#21407677)

    let mid = Math.floor((low + high) / 2);
I don't know if JS has the same problem with overflow, but seeing that expression always reminds me of https://news.ycombinator.com/item?id=14906429
Re:On Binary Search by dsego on Thursday October 31, 2019 @08:41AM (#21408070)
JS only has 64-bit floats.
Re:On Binary Search by manu3000 on Thursday October 31, 2019 @09:35PM (#21415560)
a fun exercise is to write this in Dafny https://github.com/dafny-lang/dafny

It's simple enough to be attempted with a limited knowledge of Dafny, but subtle enough that you will need to think about what you are doing

https://www.youtube.com/watch?v=-_tx3lk7yn4