Friday, March 14, 2014

Find the minimum element in a sorted and rotated array



/*
-- Base Conditions of array
-- Divide and Conquer Algorithm
-- Find middle element
-- Condition for return result
-- Condition for return left sub array
-- Condition for return right sub array
-- return result if except all test cases
*/

static int minimumElement(int[] a, int l, int r){
if (a == null || r == -1) return -1;
if(l == r) return a[l];

int m = l + (r-l)/2;

if((m-1)>=0 && a[m-1] > a[m]) return a[m];

if(a[l] > a[m]) return minimumElement(a, l, m-1);

else if(a[m] > a[r]) return  minimumElement(a, m+1, r);

return a[0];
}

References:
http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/



No comments:

Post a Comment