The article was promoted by Laser brain via FACBot ( talk) 12:13, 14 August 2018 [1].
This article is about one of the most ubiquitous algorithms in computing. Binary search is usually one of the first algorithms taught to computer science students. The premise is quite simple: given a sorted list of numbers, binary search eliminates halves of the list in which the number you are looking for cannot lie until it finds the number. However, binary search has lots of subtleties. Surprisingly, when a famous programmer asked his students to implement binary search, 90 percent could not provide a correct solution. I have wrote this article to not only cover those subtleties, but also compare binary search to other search algorithms, placing the algorithm in context. I believe that this article is FA quality as I have strived to place every relevant detail that I could find on binary search, which is surprisingly a lot of details and subtleties that the average textbook chapter on search algorithms neglects to cover. Esquivalience ( talk) 20:53, 11 June 2018 (UTC)
I think "efficiently" might be more clear here?
Kinda sorta? Phrasing is a little weird too, with "must" sounding like accountants are being ordered around. If we're talking about a hypothetical system, The opening sentence of the section already notes that constantly sorting the array is kinda inefficient; future binary searches presumably would still have to sort the array, because they aren't sure if a previous check happened and already sorted it, so it's not like the cost gets to be amortized through these. Could have an "isDirty" type function that would remember if the array has been modified since it was last sorted of course, but that's getting too much into the weeds I think.
Can the diagram ( File:Exponential search.svg) be modified to clearly be unbounded? Seems misleading at a glance... if nothing else, have the right edge with a "...".
This section is not real clear at the moment. There's something to be said for not taking too much space, and letting people who are curious about more click over to the article, but maybe give it a once-over if there's a way to still be precise but also accessible? It's great there's a diagram, but maybe call out the green highlighted section a little more in File:Fibonacci_search.png to show that section "won". If nothing else, I would recommend highlighting in the first or second sentence that rather than a specific answer (like in binary search), Fibonacci merely returns a range where the answer might be.
Why is the date it was created relevant? I'd say a description would be more helpful. "a case of the Rényi-Ulam game, a variant of twenty questions where the answers can be wrong," say.
There is no way this is possibly true as phrased - there are tons of computer-related topics, like math, that people have been giving lectures on since the ancient Babylonians. Not sure what TAOCP was saying here, but judging by the Wikipedia article, maybe something like "the first and foundational college course in computers?"
I think the article is taking Bloch & Bentley at their word a bit in a way that will confuse casual readers. Binary search, while not quite fizz buzz, is a sample easy problem generally that takes 5 minutes to solve, and surely Bentley's complaints were on hyper-specific issues. I would add in "rare edge case" or the like in discussing the overflow error in Programming Pearls and Java; it's arguably not even really an "interesting" flaw, because arrays are already size-capped in most languages to the size of the index (unsigned int, say), so this error was merely not taking advantage of the maximum amount of space available. (And heck, even with BigInteger array indices, declaring too large an array will already cause an out of memory exception unless you are on a Turing Machine with an actually-infinite tape.) SnowFire ( talk) 20:07, 13 June 2018 (UTC)
Images are appropriately licensed. Nikkimaria ( talk) 19:24, 16 June 2018 (UTC)
Support Good to see a CompSci article at FAC. Some interesting tidbits in the article. Some comments:
Great to finally see a computer science article here. Some comments on the lead to start with:
More later. Edwininlondon ( talk) 09:31, 1 July 2018 (UTC)
Edwininlondon ( talk) 18:22, 8 July 2018 (UTC)
The references need a bit of cleaning up as there are some inconsistencies:
Edwininlondon ( talk) 21:08, 10 July 2018 (UTC)
@ Edwininlondon and SnowFire: have you had a chance to review responses to your comments? Cheers, Ian Rose ( talk) 10:29, 12 August 2018 (UTC)
The article was promoted by Laser brain via FACBot ( talk) 12:13, 14 August 2018 [1].
This article is about one of the most ubiquitous algorithms in computing. Binary search is usually one of the first algorithms taught to computer science students. The premise is quite simple: given a sorted list of numbers, binary search eliminates halves of the list in which the number you are looking for cannot lie until it finds the number. However, binary search has lots of subtleties. Surprisingly, when a famous programmer asked his students to implement binary search, 90 percent could not provide a correct solution. I have wrote this article to not only cover those subtleties, but also compare binary search to other search algorithms, placing the algorithm in context. I believe that this article is FA quality as I have strived to place every relevant detail that I could find on binary search, which is surprisingly a lot of details and subtleties that the average textbook chapter on search algorithms neglects to cover. Esquivalience ( talk) 20:53, 11 June 2018 (UTC)
I think "efficiently" might be more clear here?
Kinda sorta? Phrasing is a little weird too, with "must" sounding like accountants are being ordered around. If we're talking about a hypothetical system, The opening sentence of the section already notes that constantly sorting the array is kinda inefficient; future binary searches presumably would still have to sort the array, because they aren't sure if a previous check happened and already sorted it, so it's not like the cost gets to be amortized through these. Could have an "isDirty" type function that would remember if the array has been modified since it was last sorted of course, but that's getting too much into the weeds I think.
Can the diagram ( File:Exponential search.svg) be modified to clearly be unbounded? Seems misleading at a glance... if nothing else, have the right edge with a "...".
This section is not real clear at the moment. There's something to be said for not taking too much space, and letting people who are curious about more click over to the article, but maybe give it a once-over if there's a way to still be precise but also accessible? It's great there's a diagram, but maybe call out the green highlighted section a little more in File:Fibonacci_search.png to show that section "won". If nothing else, I would recommend highlighting in the first or second sentence that rather than a specific answer (like in binary search), Fibonacci merely returns a range where the answer might be.
Why is the date it was created relevant? I'd say a description would be more helpful. "a case of the Rényi-Ulam game, a variant of twenty questions where the answers can be wrong," say.
There is no way this is possibly true as phrased - there are tons of computer-related topics, like math, that people have been giving lectures on since the ancient Babylonians. Not sure what TAOCP was saying here, but judging by the Wikipedia article, maybe something like "the first and foundational college course in computers?"
I think the article is taking Bloch & Bentley at their word a bit in a way that will confuse casual readers. Binary search, while not quite fizz buzz, is a sample easy problem generally that takes 5 minutes to solve, and surely Bentley's complaints were on hyper-specific issues. I would add in "rare edge case" or the like in discussing the overflow error in Programming Pearls and Java; it's arguably not even really an "interesting" flaw, because arrays are already size-capped in most languages to the size of the index (unsigned int, say), so this error was merely not taking advantage of the maximum amount of space available. (And heck, even with BigInteger array indices, declaring too large an array will already cause an out of memory exception unless you are on a Turing Machine with an actually-infinite tape.) SnowFire ( talk) 20:07, 13 June 2018 (UTC)
Images are appropriately licensed. Nikkimaria ( talk) 19:24, 16 June 2018 (UTC)
Support Good to see a CompSci article at FAC. Some interesting tidbits in the article. Some comments:
Great to finally see a computer science article here. Some comments on the lead to start with:
More later. Edwininlondon ( talk) 09:31, 1 July 2018 (UTC)
Edwininlondon ( talk) 18:22, 8 July 2018 (UTC)
The references need a bit of cleaning up as there are some inconsistencies:
Edwininlondon ( talk) 21:08, 10 July 2018 (UTC)
@ Edwininlondon and SnowFire: have you had a chance to review responses to your comments? Cheers, Ian Rose ( talk) 10:29, 12 August 2018 (UTC)