Only 10% of programmers are able to write a binary search.
Donald Knuth (known for not reading his books) writes that although the first binary search was published in 1946, the first binary search without bugs was published only in 1962.
The binary search algorithm is similar to how we search for a word in a dictionary. Open the dictionary in the middle, look at which of the halves will be the word we need. For example, in the first. Open the first part in the middle, continue to half until we find the right word.
With arrays like this: there is an ordered array, we take a number from the middle of the array, compare it with the desired one. If it turned out to be more, then the required number in the first half of the array, if less - in the second. We continue to divide the remaining half, when we find the desired number, we return its index, if we don’t find it, we return null.
')
The article stated that only 10% of programmers can solve this problem. Do not you say! That suckers, I thought, loaded Firebug, some 5 minutes and ... non-working version is ready. Another iteration, and more, and more. In total, an hour and a half, and in the final decision there are still 2 errors. It's a shame how!
If you have never written a binary search, I suggest you write this algorithm in your favorite language and put it in comments without testing . Any good programmer will immediately write this truly children's algorithm. Spend as much time as you need. In the comments, indicate the language, the time spent, and a link to your work at pastie.org .
Wikipedia has the right solution .
A small gift for those to whom it all seems commonplace. Almost all implementations of binary search and merge sort have errors . This is said the person who wrote the binary search for the JDK.
Spoiler
Common mistakes:
- does not work with an array of 0/1/2 elements
- does not find the first or last element
- does not work correctly if there is no element in the array
- does not work correctly if there are duplicate elements in the array
- appeal to elements outside the array
- trump, which was in JDK, integer overflow in calculating the average index
PS
Someone will say that this function is already in the standard library.
This is so agree. But this does not mean that there is no sense in solving such problems. See, if all the simple tasks are already solved for us in the standard library, then we have only the more complex tasks that are not there. How will we solve these more complex problems if we are not able to solve even a simple task from the standard library?
I'll tell you how. Very bad. I did code checking when I was working in a team. Many programmers could not give birth to the simplest code, even with 20 attempts! They are used to sitting at the ready, and are not able to write something more complicated than foo (bar ()) composition, and if they do, the implementation will be slow, confusing, and with errors.
The binary search algorithm is similar to how we search for a word in a dictionary. Open the dictionary in the middle, look at which of the halves will be the word we need. For example, in the first. Open the first part in the middle, continue to half until we find the right word.
With arrays like this: there is an ordered array, we take a number from the middle of the array, compare it with the desired one. If it turned out to be more, then the required number in the first half of the array, if less - in the second. We continue to divide the remaining half, when we find the desired number, we return its index, if we don’t find it, we return null.
')
The article stated that only 10% of programmers can solve this problem. Do not you say! That suckers, I thought, loaded Firebug, some 5 minutes and ... non-working version is ready. Another iteration, and more, and more. In total, an hour and a half, and in the final decision there are still 2 errors. It's a shame how!
If you have never written a binary search, I suggest you write this algorithm in your favorite language and put it in comments without testing . Any good programmer will immediately write this truly children's algorithm. Spend as much time as you need. In the comments, indicate the language, the time spent, and a link to your work at pastie.org .
Wikipedia has the right solution .
A small gift for those to whom it all seems commonplace. Almost all implementations of binary search and merge sort have errors . This is said the person who wrote the binary search for the JDK.
Spoiler
Common mistakes:
- does not work with an array of 0/1/2 elements
- does not find the first or last element
- does not work correctly if there is no element in the array
- does not work correctly if there are duplicate elements in the array
- appeal to elements outside the array
- trump, which was in JDK, integer overflow in calculating the average index
PS
Someone will say that this function is already in the standard library.
This is so agree. But this does not mean that there is no sense in solving such problems. See, if all the simple tasks are already solved for us in the standard library, then we have only the more complex tasks that are not there. How will we solve these more complex problems if we are not able to solve even a simple task from the standard library?
I'll tell you how. Very bad. I did code checking when I was working in a team. Many programmers could not give birth to the simplest code, even with 20 attempts! They are used to sitting at the ready, and are not able to write something more complicated than foo (bar ()) composition, and if they do, the implementation will be slow, confusing, and with errors.
Source: https://habr.com/ru/post/91605/
All Articles