Search in a bitonic array

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:

  1. If  A[I-1] < A[I] < A[I+1], A[I] is not the turning point and we are stilling in the ascending sequence;
  2. If A[I-1] > A[I] > A[I+1], A[I] is not the turning point and we are in the descending sequence;
  3. 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:

Enhanced by Zemanta
Advertisements
Search in a bitonic array

3 thoughts on “Search in a bitonic array

  1. Hi there, I came across this post when trying to solve the same problem. In your solution, you use the same binary search for both the increasing and decreasing portions. Why don’t you need to create a modified version of binary search to handle the decreasing array?

    1. Ah, I think you are right. for the second half we probably need to modify the binary search. Thank you for pointing that out. Are you taking the Algorithms Course on Coursera? This is actually one of the homework I think.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s