zxt-tzx / bitonic-array-search

Searching a Bitonic Array

A bitonic sequence is a sequence of numbers that is first strictly increasing then after a point strictly decreasing. (Imagine a mountain with a peak.) This goal is to write a program that can find a target element in an array containing a bitonic sequence (hereafter “bitonic array”). Assume there is no consecutive duplicate elements.

Binary search

Using binary search, it is pretty easy to find an element in O(log n) time.

1. Find the “peak” in the bitonic array.
2. Use the “peak” to demarcate the bitonic array into a left half and a right half.
3. Use binary search to search one half of the array. Return the element if found. If not, search the other half of the array.

In the worst case, this will take 3 binary searches, i.e. ~3 log n. However, the challenge is: can we do better?

Binary search, modified

Let’s first observe some characteristics of binary search and a bitonic array. In each run of binary search, the relative position of nums[mid] helps to inform which part of the array to search next. In a regular sorted array, this is simply done by comparing whether nums[mid] is bigger or smaller than the target and discarding the other half of the array accordingly.

In a bitonic array, this is a little more subtle. There are two key insights.

First, if we can deduce whether target is to the left or the right of nums[mid], we can recursively call the same function on the rest of the sub-array (which is itself a bitonic array) and discard the other half of the array where we know the target cannot exist.

This is given by the following two conditions:

• nums[mid - 1] < nums[mid] and nums[mid] < target: in this case, we know target is definitely not in nums[:mid]. We can search the right half of the array using the same function.
• nums[mid - 1] > nums[mid] and nums[mid] < target: in this case, we know target is definitely not in nums[mid:]. We can search the left half of the array using the same function.

However, what should we do in the last two scenarios, nums[mid - 1] < nums[mid] and nums[mid] > target and nums[mid - 1] < nums[mid] and nums[mid] < target? In these two scenarios, the target could be in either half of the array. How can we continue to zero onto the target?

The second insight is: we can actually binary search an array that isn’t properly sorted, as long as we know it is sorted relative to the target. Notice that in both scenarios, nums[mid] > target. This means that we can apply an ascending binary search to the the sub-array nums[:mid] and a descending binary search to the sub-array nums[mid:]. In an ascending binary search of nums[:mid], any element that is larger than nums[mid] will necessarily also be larger than target. Thus, even if the sub-array is not properly sorted, we can still deduce which half of the array to discard by comparing every element to target. The same reasoning applies mutatis mutandis to the descending binary search for target in nums[mid:].

As such, by running ascending and descending binary searches on both halves of the array when nums[mid] > target, we can find target in ~log n time, instead of the ~3 log n time of the previous solution.