Reply to thread

Message: [QUOTE="Juha Nieminen, post: 3587091"] You can't do that with one single comparison. In order to do that you would have to first look if the 4th element is equal to the searched element, and if it isn't, then you have to look if it's smaller (in order to decide which half you discard), after which you can continue with the correct half without the 4th element included. That would make two comparisons per step. The total number of comparisons in the worst case would grow to at least 5 (depending on how you implement the check for a range of one single element). In order to have only one comparison per step, you have to look if the 4th element is smaller than the searched element, and then choose the correct half *including* that 4th element. (You can't discard it because it might actually be the searched element.) That is, the first step discards 3 elements and continues with the remaining 4. This way the total number of comparisons in the worst case is 4. [/QUOTE]