Problem statement:
Given an bitonic array, find the max element in that.
Example:
Array {1, 2, 3, 4, 5, 4, 3, 2, 1};
key = 1
Output = 0 or 9
A bitonic array is an ascending sorted array where, after a particular element, the array starts descending.
In our example above, the array is ascending till element 5 and starts descending after that.
Solution:
We can solve this with help of binary search and peak element.
First we need to find the peak element and dvide the array into 2 halves.
Then apply binary search in both of the halves.
Solution:
#include <iostream> using namespace std; int find_peak_element_index(int arr[], int len) { int start = 0; int end = len - 1; while (start <= end) { int mid = (start + end) / 2; if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == len - 1 || arr[mid] >= arr[mid + 1])) { return mid; } else if (mid > 0 && arr[mid - 1] > arr[mid]) { end = mid - 1; } else { start = mid + 1; } } return -1; } int ascending_binary_search(int arr[], int start, int end, int key) { while (start <= end) { int mid = start + (end - start) / 2; if (arr[mid] == key) return mid; if (arr[mid] > key) end = mid - 1; else start = mid + 1; } return -1; } int descending_binary_search(int arr[], int start, int end, int key) { while (start <= end) { int mid = start + (end - start) / 2; if (arr[mid] == key) return mid; if (arr[mid] < key) end = mid - 1; else start = mid + 1; } return -1; } int binary_search( int arr[], int len, int peak_index, int key) { if (key > arr[peak_index]) return -1; else if(key == arr[peak_index]) return peak_index; else { int temp = ascending_binary_search(arr, 0, peak_index - 1, key); if (temp != -1) { return temp; } return descending_binary_search(arr, peak_index + 1, len - 1, key); } } int main(void) { int arr[] = {1, 2, 3, 4, 5, 4, 3, 2, 1}; int len = sizeof(arr) / sizeof(arr[0]); int key = 1; int peak_index = find_peak_element_index(arr, len); int result = binary_search(arr, len, peak_index, key); cout<<"The key element "<<key<<" is found at the index " <<result<<endl; return 0; }
Output:
The key element 1 is found at the index 0