Q: Search in a bitonic array. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct integer values, determines whether a given integer is in the array.
- Standard version: Use ∼3lgN compares in the worst case.
- Signing bonus: Use ∼2lgN compares in the worst case (and prove that no algorithm can guarantee to perform fewer than ∼2lgN compares in the worst case).
(Java Code on github at the bottom of the post. )
My thoughts and solutions:
Well, we could just go for linear search but that takes O(N) time. The question requires O(lgN). The only search with O(N) time I know is binary search, which requires a sorted array. We have a bitonic array. Well in some sense it consists of two sorted parts with a turning point in between. For example:
1, 2, 4, 7, 10, 9, 5, 3, 0
So if I know where the turning point is, I could just apply binary search on both sorted parts. That takes 2lgN. How do we find the turning point? Again, we could use linear search with O(N) time, but then there’s no point of doing any of these things above. The standard version is 3lgN. We used 2lgN, so I guess finding the turning point uses the left lgN time, with a binary search.
But how do we apply binary search to find the turning point? Think about the characteristics of a turning point. Say we look at the element at index I:
- If A[I-1] < A[I] < A[I+1], A[I] is not the turning point and we are stilling in the ascending sequence;
- If A[I-1] > A[I] > A[I+1], A[I] is not the turning point and we are in the descending sequence;
- If A[I-1] < A[I] > A[I+1], then A[I] is the turning point.
Then we can apply binary search on it and instead of looking for a specific element, we look for the element with the 3rd characteristic. In this way, we can find the turning point and the rest is easy.
As for the 2lgN, I’m still working on it…Probably I have to eliminate one binary search here, but which one and how?
Code on github: