On Binary Search

http://unfolding-programming.net/essays/2019-10-30-on-binary-search

by _4bcr • 7 years ago

49 40 7 years ago

j-pb• 7 years ago

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.

person_of_color2• 7 years ago

Good for interview prep, then!

claes-magnus8• 7 years ago

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. :)

RcouF1uZ4gsC• 7 years ago

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.

adrianmonk3• 7 years ago

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.

tempguy99992• 7 years ago

Agreed. It's such a strange statement I suspect he meant something else but I can't see what.

adrianmonk3• 7 years ago

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."

akamoonknight• 7 years ago

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.

devnonymous• 7 years ago

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.

smitty1e• 7 years ago

Working in IT affords occasion to be humble at least daily.

person_of_color2• 7 years ago

Why does this implementation used signed integers for indices at all?

MauranKilom2• 7 years ago

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.

agentultra• 7 years ago

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.

hansdieter1337• 7 years ago

"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?

MauranKilom2• 7 years ago

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/

idbfs• 7 years ago

I was wondering the same thing. It's either a horrible human-written article, or an impressive machine-written one.

gigatexal• 7 years ago

It could be a non-native speaker of English trying his or her best.

claes-magnus8• 7 years ago

@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!

claes-magnus8• 7 years ago

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!

smellia2• 7 years ago

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.

claes-magnus8• 7 years ago

@smellia: thank you very much for this suggestion! This seems really interesting. :)

kqr• 7 years ago

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!

claes-magnus8• 7 years ago

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. :( :)

carapace• 7 years ago

Keep up the good work! :-)

userbinator• 7 years ago

    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

dsego• 7 years ago

JS only has 64-bit floats.

bla32• 7 years ago

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 :)

bla32• 7 years ago

The highest-rated comment on https://stackoverflow.com/questions/504335/what-are-the-pitf... is also good.

claes-magnus8• 7 years ago

Thank you!

xrisk• 7 years ago

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...

OrWestSide• 7 years ago

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 :)

claes-magnus8• 7 years ago

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. :)

manu3000• 7 years ago

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

On Binary Search

Related Stories