Let A[1 . . . n] be an array of n distinct integers. We say that A is peaked, if
ID: 3877642 • Letter: L
Question
Let A[1 . . . n] be an array of n distinct integers. We say that A is peaked, if there exists an index 1 k n such that: (1) For all 1 i < k, A[i] < A[i + 1] and (2) for all k < i n, A[i 1] > A[i]. That is, the array increases until k and decreases afterward. Call the index k the peak of A. Describe an algorithm which in O(log n) time finds the peak of a given peaked array A[1 . . . n] consisting of n distinct integers. Specifically, give short descriptions of how your algorithm works, why it is correct, and why it achieves the stated running time
Explanation / Answer
Modified Binary Search
We can modify the Binary Search algorithm for our algorithm.
i) If the middle element is greater than both of its adjacent elements, then middle is the maximum.
ii) If middle element is greater than its next element and smaller than the previous element then maximum lies on left side of middle. Example array: {6, 53, 13, 12, 10, 9} mid element 13, next 12, previous 53
iii) If middle element is smaller than its next element and greater than the previous element then maximum lies on right side of mid. Example array: {7, 9, 11, 13, 15, 8, 6} here mid is 13 , next element is 15, previous element is 13.
int findMaximumIndex(int arr[], int low, int high)
{
/* Base Case: only one element*/
if (low == high)
return low;
/* If two elements and first is greater then the first element is maximum */
if ((high == low + 1) && arr[low] >= arr[high])
return low;
/* If two elements and second is greater then first
the second element is maximum */
if ((high == low + 1) && arr[low] < arr[high])
return high;
int mid = (low + high)/2;
/* If we reach a point where arr[mid] is greater than both of
its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
is the maximum element*/
if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
return mid;
/* If arr[mid] is greater than the next element and smaller than the previous
element then maximum lies on left side of mid */
if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
return findMaximumIndex(arr, low, mid-1);
else // when arr[mid] is greater than arr[mid-1] and smaller than arr[mid+1]
return findMaximumIndex(arr, mid + 1, high);
}
Time Complexity: O(Logn)
int findMaximumIndex(int arr[], int low, int high)
{
/* Base Case: only one element*/
if (low == high)
return low;
/* If two elements and first is greater then the first element is maximum */
if ((high == low + 1) && arr[low] >= arr[high])
return low;
/* If two elements and second is greater then first
the second element is maximum */
if ((high == low + 1) && arr[low] < arr[high])
return high;
int mid = (low + high)/2;
/* If we reach a point where arr[mid] is greater than both of
its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
is the maximum element*/
if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
return mid;
/* If arr[mid] is greater than the next element and smaller than the previous
element then maximum lies on left side of mid */
if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
return findMaximumIndex(arr, low, mid-1);
else // when arr[mid] is greater than arr[mid-1] and smaller than arr[mid+1]
return findMaximumIndex(arr, mid + 1, high);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.