Answer:
The solution is Based on binary Search
The idea is to find the bitonic point k which is the index of the maximum element of given sequence. If the element to be searched is greater than maximum element return -1, else search the element in both halves. Below is the step by step algorithm on how to do this.
- Find the bitonic point in the given array, i.e the maximum element in the given bitonic array. This can be done in log(n) time by modifying the binary search algorithm. You can refer to this post on how to do this.
- If the element to be searched is equal to the element at bitonic point then print the index of bitonic point.
- If the element to be searched is greater than element at bitonic point then element does not exist in the array.
- If the element to be searched is less than element at bitonic point then search for element in both half of the array using binary search.
Time complexity: O(logn)
Space complexity: O(1)
