Friday, December 5, 2014

Microsoft Question: Find the pivot element in an array in which elements are first in strictly decreasing and then in strictly increasing order.

Question: 
You are given an array in which elements are first in strictly decreasing and then in strictly increasing order. You need to find the index of pivot element in that array.
For example: arr = {6, 4, 2, 4, 6} then index of pivot element is 2.

Solution:
Modify binary search for this particular problem.

int findPivotInDecIncArray(int *arr, int left, int right)
{
        int mid = left + (right - left) / 2;
        if(left > right)
                return -1;
        if(arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1])
                return mid;
        if(arr[mid] <  arr[mid -1] && arr[mid] > arr[mid + 1])
                return findPivotInDecIncArray(arr, mid + 1, right);
        if(arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1])
                return findPivotInDecIncArray(arr, left, mid - 1);
        return -1;

No comments:

Post a Comment