11 Apr 2018

Problem Description

• 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).

Personal Thoughts

• Assume the array is of size n. The minimum value for n is 3. We can find the index of the turning point, t, in the array with ∼logn time through following procedure:
  • initialize l = 0, r = n – 1.
  • get the middle item of the array, m = l + (r – l) / 2 => arr[m]
  • compare arr[m] against the item right before it, a and the item right after it, b
  • if arr[m] > a and arr[m] > b, return m
  • if arr[m] > a and arr[m] < b, apply recursive call on the method (set l = m)
  • if arr[m] < a and arr[m] > b, apply recursive call on the method (set r = m)
• compare the search term, s with the turning point, arr[t]:
  • if s > arr[t], return – 1 (the search term is not in the array)
  • else if s == arr[t], return t
  • else, conduct an ascending binary search on the part before t (∼logn time) and a descending binary search on the part after t (∼logn time)
• ascending binary search:
  • initialize l = 0, r = n – 1
  • set up a while loop with terminating condition l <= r
  • initialize m = l + (r – l) / 2
  • if arr[m] == s, return m
  • else if arr[m] < s, l = m + 1
  • else, r = m – 1 and if not found, return -1
• descending binary search:
  • initialize l = 0, r = n – 1
  • set up a while loop with terminating condition l <= r
  • initialize m = l + (r – l) / 2
  • if arr[m] == s, return m
  • else if arr[m] < s, r = m – 1
  • else, l = m + 1 and if not found, return -1

Java Implementation