Anonymous user
Binary search: Difference between revisions
no edit summary
No edit summary |
|||
Line 36:
return not_found
}
;Extra credit
Make sure it does not have overflow bugs.
The line in the pseudocode above to calculate the mean of two integers:
<code>mid = (low + high) / 2</code>
could produce the wrong result in some programming languages when used with a bounded integer type, if the addition causes an overflow. (This can occur if the array size is greater than half the maximum integer value.) If signed integers are used, and <code>low + high</code> overflows, it becomes a negative number, and dividing by 2 will still result in a negative number. Indexing an array with a negative number could produce an out-of-bounds exception, or other undefined behavior. If unsigned integers are used, an overflow will result in losing the largest bit, which will produce the wrong result.
One way to fix it is to manually add half the range to the low number:
<code>mid = low + (high - low) / 2</code>
Even though this is mathematically equivalent to the above, it is not susceptible to overflow.
Another way for signed integers, possibly faster, is the following:
<code>mid = (low + high) >>> 1</code>
where <code> >>> </code> is the logical right shift operator. The reason why this works is that, for signed integers, even though it overflows, when viewed as an unsigned number, the value is still the correct sum. To divide an unsigned number by 2, simply do a logical right shift to the right.
=={{header|Ada}}==
Both solutions are generic. The element can be of any comparable type (such that the operation < is visible in the instantiation scope of the function Search). Note that the completion condition is different from one given in the pseudocode example above. The example assumes that the array index type does not overflow when mid is incremented or decremented beyond the corresponding array bound. This is a wrong assumption for Ada, where array bounds can start or end at the very first or last value of the index type. To deal with this, the exit condition is rather directly expressed as crossing the corresponding array bound by the coming interval middle.
| |||