You have an array A[0], A[1], ..., A[n - 1] of distinct integers that has the fo

Question

You have an array A[0], A[1], ..., A[n - 1] of distinct integers that has the following property:The values in the array increase up to index p for some p between 0 and n - 1, and then decrease for all indices beyond p through position n-1.You want to find the p index at which the peak value occurs. Describe a divide-and-conquer algorithm that can solve this problem in?(lg n) time, where the work unit is comparison of array values. Do a formal analysis to prove this. you can assume that n is a power of 2.

Explanation / Answer

pivot element is the only only element for which next element to it is smaller than it. we can use this condition and binary search to find the pivot as follows:

return value of this function will give the index of pivot element.

int pivot(int arr[], int low, int high)

{

   // base cases

   if (high < low) return -1;

   if (high == low) return low;

   int mid = (low + high)/2;   /*low + (high - low)/2;*/

   if (mid < high && arr[mid] > arr[mid + 1])

     return mid;

   if (mid > low && arr[mid] < arr[mid - 1])

     return (mid-1);

   if (arr[low] >= arr[mid])

     return pivot(arr, low, mid-1);

   else

     return pivot(arr, mid + 1, high);

}

Since we know that binary search is of theta(logn) here also we are dividing array into two equal parts ...

hence the time complexity of this also is theta(logn)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.