Sort And Searching Interview Question:

What is Bitonic search?

Submitted by: Muhammad

An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Given a bitonic array a of N distinct integers, describe how to determine whether a given integer is in the array in O(log N) steps. Hint: find the maximum, then binary search in each piece.
Submitted by: Muhammad