1. An array A[O..n-1] of n distinct numbers is bitonic if there are unique indices i and j such that A[(i-1) mod n]

[answerhappygod]

1 An Array A O N 1 Of N Distinct Numbers Is Bitonic If There Are Unique Indices I And J Such That A I 1 Mod N A I 1 (140.04 KiB) Viewed 38 times

1. An array A[O..n-1] of n distinct numbers is bitonic if there are unique indices i and j such that A[(i-1) mod n] <A > A[(i+1) mod n] and A[G - 1) mod n] > A[j] < A[G] +1) mod n]. In other words, a bitonic sequence either consists of an increasing sequence followed by a decreasing sequence, or can be circularly shifted to become so. For example, 461918675123 is bitonic, but 360981751 24 is not bitonic. Describe and analyze an algorithm to find the index of the smallest element in a given bitonic array A[0..n-1) in O(log n) time. You may assume that the numbers in the input array are distinct. For example, given the first array above, your algorithm should return 6, because A[6] = 1 is the smallest element in that array.