Wikipedia:Peer review/Binary search algorithm/archive1

Comments by Mike Christie

Making my way through the article; this looks in good shape. Some comments below.

• I'd suggest linking to Big O notation the first time you use it.
• A related point: most people won't know that notation, so could it be avoided or explained in the lead? I can imagine many readers wanting to learn about binary search without having a maths background; if we can introduce the technical terms gradually that would help. Non-technical readers aren't going to get to the end of the article, but they should be able to get through the first section or two, if they're motivated.
• Why is the information in the performance section about pre-storing certain locations in an invisible comment, rather than a note or part of the text? It seems like useful information.
• You explain the floor function, but by that time you've already used it in the algorithm. It's linked there, but it might be better to avoid using it in the algorithm, so you can explain it on first use. In the algorithm just paraphrase what it does.
• Similarly you explain "amortized" on second use.
• I see you're using "log" for log₂, after defining it in the lead. Unless the sources don't do this (perhaps because "log" always means "log₂" in the literature?) I think the subscript would be helpful. In any case the information should be repeated in the body, since the lead shouldn't contain anything not in the body.
• Any reason not to put the arguments in parentheses in expressions such as "log n - 1"?
• "no search algorithm that is based solely on comparisons": how about a footnote that links to an article about algorithms that are not based solely on comparisons? It's not immediately obvious what these might be, but perhaps the information doesn't belong in the main text.
• The Judy array sentence isn't really very informative as it stands; if these are worth mentioning, a few more words of description would be helpful. Also, the sentence is unsourced as is the following paragraph, and at least one later paragraph.
• I'd suggest thickening the line in the Fibonacci search illustration; on one of my two screens (1920 x 1080) the line looks OK, but on the other (1280 x 1024) it's almost invisible.
• "interpolation search is slower than binary search for small arrays, as interpolation search requires extra computation, and the slower growth rate of its time complexity compensates for this only for large arrays": does Knuth give any specifics on the minimum array size at which interpolation search becomes more efficient?
• In the history section, I'd rephrase the mention of fractional cascading -- you describe it in the paragraph just above so it can be referred to as something the reader has already been told about, rather than as something that needs an explanation.
• I found the note about the overflow bug in Bentley's (and other) implementations fascinating, particularly because I read Bentley's original article thirty years ago. I'd suggest changing the start of the following paragraph to make it clearer that you're about to explain the problem; as it stands I thought the new paragraph was going on to another topic till I was halfway through it.

-- Mike Christie (talk - contribs - library) 10:51, 21 October 2016 (UTC)

@Mike Christie: "A related point: most people won't know that notation, so could it be avoided or explained in the lead?"

Er... that's tricky. It's a fairly involved subject, and more to the point it's absolutely basic computer science, which a lot of people interested in this subject matter would already have encountered. (Admittedly binary search is also absolutely basic computer science, so that sets something of an upper limit on the expertise of the readers.)

What I think would read better is to keep the clutter out of the lead and not try to explain the (tangential issue of the) notation there. Rather, since binary search is the textbook example of an O(log n) algorithm, I'd postpone the description to the section on "performance" which describes its performance at greater length and the describes O() notation in terms of that.

Just MHO. 71.41.210.146 (talk) 06:07, 24 December 2016 (UTC)