2. Suppose we are given an array A[1..n] with the boundary conditions that A[1]

Question

2. Suppose we are given an array A[1..n] with the boundary conditions that A[1] A[2] and A[n 1] A[n]. We say that an element A[x] is a local minimum if it is less than or equal to both its neighbors, or more formally, if A[x 1] A[x] and A[x] A[x + 1]. For example, there are six local minima in the following array:

9 | 7 | 7 | 2 | 1 | 3 | 7 | 5 | 4 | 7 | 3 | 3 | 4 | 8 | 6 | 9

We can obviously find a local minimum in O(n) time by scanning through the array. This problem leads you to a faster algorithm.

1 (a) Describe a divide-and-conquer algorithm that, given an array A[1..n] with the boundary conditions mentioned above, finds and returns a local minimum in O(log n) time. You can assume that n 3. Hint: With the given boundary conditions, the array must have at least one local minimum. Why?

(b) Prove the correctness of your algorithm.

(c) Write down a recurrence for the running time of your algorithm. You do not have to solve this recurrence.

Explanation / Answer

Hi, Please find my Algorithm and Function.

An efficient solution is based on Binary Search.
Steps:

1. We compare middle element with its neighbors.
2. If middle element is not greater than any of its neighbors, then we return it.
3. If the middle element is greater than its left neighbor, then there is always a local minima in left half .
4. If the middle element is greater than its right neighbor, then there is always a local minima in right half (due to same reason as left half).

// A wrapper over recursive function localMinUtil()
int localMin(int arr[], int n)
{
return localMinUtil(arr, 0, n-1, n);
}

// A binary search based function that returns
// index of a local minima.
int localMinUtil(int arr[], int low, int high, int n)
{
// Find index of middle element
int mid = low + (high - low)/2; /* (low + high)/2 */

// Compare middle element with its neighbours
// (if neighbours exist)
if ((mid == 0 || arr[mid-1] > arr[mid]) &&
(mid == n-1 || arr[mid+1] > arr[mid]))
return mid;

// If middle element is not minima and its left
// neighbour is smaller than it, then left half
// must have a local minima.
else if (mid > 0 && arr[mid-1] < arr[mid])
return localMinUtil(arr, low, (mid -1), n);

// If middle element is not minima and its right
// neighbour is smaller than it, then right half
// must have a local minima.
return localMinUtil(arr, (mid + 1), high, n);
}

Time complexity: O(logN)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

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