Find bitonic point in given bitonic sequence - GeeksforGeeks

Find bitonic point in given bitonic sequence - GeeksforGeeks

You are given a bitonic sequence, the task is to find Bitonic Point in it. A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.

A Bitonic Point is a point in bitonic sequence before which elements are strictly increasing and after which elements are strictly decreasing. A Bitonic point doesn't exist if array is only decreasing or only increasing.

Examples:

Input : arr[] = {6, 7, 8, 11, 9, 5, 2, 1}  Output: 11  All elements before 11 are smaller and all  elements after 11 are greater.    Input : arr[] = {-3, -2, 4, 6, 10, 8, 7, 1}  Output: 10  

We strongly recommend you to minimize your browser and try this yourself first.

A simple solution for this problem is to use linear search. Element arr[i] is bitonic point if both i-1'th and i+1'th both elements are less than i'th element. Time complexity for this approach is O(n).

An efficient solution for this problem is to use modified binary search.

• If arr[mid-1] < arr[mid] > arr[mid+1] then we are done with bitonic point.
• If arr[mid] < arr[mid+1] then search in right sub-array, else search in left sub-array.

Read full article from Find bitonic point in given bitonic sequence - GeeksforGeeks