Searching a sorted array

If the target is present at all, its index lies between lo and hi inclusive

The element at mid is always closer to the target than the endpoints

The interval always contains exactly half the remaining elements

lo is always less than the target and hi always greater

the algorithm needs at least {n}{+}{1} distinct leaves, and a binary tree of height {h} has at most {{2}}^{{h}}

every comparison halves the array

the array must be sorted first

{n}{+}{1} elements must each be compared once

it uses the value of the key to guess a position, so the comparison lower bound does not apply to it

it makes two comparisons per round instead of one

it does not require sorted data

it has a better worst case than binary search

The sum can overflow a fixed-width integer, which shipped as a bug in Java's Arrays.binarySearch for nine years

It gives a different midpoint that converges faster

Division is cheaper on a subtraction

It handles unsorted arrays correctly

True

False

Reaching the middle element costs {\Theta }{(}{n}{)} hops, destroying the saving

The total cost becomes {\Theta }{(}{n}{)}

The ordering property still holds, so the halving argument is still valid

The comparison count rises to {\Theta }{(}{n}{log}{n}{)}