# bitonic.py

'''
Introduction to Programming in Python
Robert Sedgewick, Kevin Wayne, Robert Dondero
Addison-Wesley, 2015
Ex 4.2.20 Bitonic maximum
https://introcs.cs.princeton.edu/python/41analysis/

An array is bitonic if it consists of an increasing sequence of 
keys followed immediately by a decreasing sequence of keys. 
Given a bitonic array, design a logarithmic algorithm to find 
the index of a maximum key.

An efficient solution is to use modified binary search. 
'''

def bitoSearch(elems, left, right):
  if (left <= right):
    mid = (left + right) // 2;
  
    # check if elems[mid] is max bitonic
    if (elems[mid-1] < elems[mid]) and (elems[mid] > elems[mid + 1]):
      return mid;
  
    # Go to right if middle point is part of increasing 
    # subsequence, else go left
    if (elems[mid] < elems[mid + 1]):
      return bitoSearch(elems, mid+1, right);
    else:
      return bitoSearch(elems, left, mid-1);
  return -1;
  
# ------------ main ------------------

elems = [6, 7, 8, 11, 9, 5, 2, 1];

print("Max at:", bitoSearch(elems, 1, len(elems)-2))