A bitonic array is an array A such that there is some index i, where the values
ID: 3905905 • Letter: A
Question
A bitonic array is an array A such that there is some index i, where the values in A are increasing from index 1 to i, and decreasing from index i to the end of the array. Design a divide?and?conquer algorithm to find the maximum element in a bitonic array. Analyze its running time with the Master Theorem.
Hint: This is very simple to binary search. You want to nd the point where the array stops increasing and starts decreasing. How can you tell whether that is to the left or right of your current location?
Explanation / Answer
Hello Student!
I am happy to help you!
************************Code starts here************************
// Bitonic main function
int bitonicPt(int inp_arr[] ,int n, int left, int right) {
int mid = (right + left) / 2;
// return mid if you found the point
if(inp_arr[mid] > inp_arr[mid-1] && inp_arr[mid] > inp_arr[mid + 1]) {
return mid;
}
// recursively call to mid till right
if(inp_arr[mid] > inp_arr[mid - 1] && inp_arr[mid] < inp_arr[mid + 1]) {
bitonicPt(inp_arr,n, mid , right);
}
// recursively call to left till mid
if(inp_arr[mid] < inp_arr[mid - 1] && inp_arr[mid] > inp_arr[mid + 1]) {
bitonicPt(inp_arr, n, left, mid);
}
return -1;
}
// main code
int main() {
int inp_arr[] = {-3, 9, 8, 20, 17, 5, 1};
int n = sizeof(inp_arr)/sizeof(inp_arr[0]);
int left = 0, right = n - 1, idx;
idx = bitonicPt(inp_arr, n, left, right);
cout << "Bitonic point is : " << idx << endl;
int ans = inp_arr[idx];
if (idx-1 >= 0) {
ans = max(ans, inp_arr[idx-1]);
}
if (idx+1 < n) {
ans = max(ans, inp_arr[idx+1]);
}
cout << "Maximum element is :" << ans << endl;
return 0;
}
*****************Code ends here********************
Test Case :
Bitonic point is : 3
Maximum element is :20
Program ended with exit code: 0
Time complexity : O(logn)
Using master's theorem
T(n) = T(n/2) + O(1)
a = 1 ; b = 2 ; c = 0
0 < log2(1)
0 = 0
O(nclogn)
c = 0
O(logn)
Hence proved.
Thank you. Feel free to ask anything. If you like the answer. Please upvote it. It means a lot. Thank you again.