CareerCup

So do you want to return the elements position of duplicates too?

If we know the size of an array, get the first element of an array (ascending order) and get the last element of an array(descending order), whichever is smaller return that element,

if we need to find position also, once we find the smallest just increment or decrement array index until the smaller returned element value matches.

int  a[] = {4, 5, 8, 9, 11, -1, 0, 3, 2};

    int x = a[0];

    int l = 1;
    int r = sizeof(a) / sizeof(a[0]) - 1;

    while (l < r - 1) {
        int m = (l + r) / 2;

        if (a[m] > x)
            l = m;
        if (a[m] <= x)
            r = m;
    }

    cout << "min = " << a[r] << endl;

simple recursive solution

# include <iostream>

using namespace std;

int MinElement(int *arr, int low, int high)
{
 int mid;
 
 if(low > high)
  return -1;

 
 mid = (low + high)/2;

 if(arr[mid] - arr[mid-1] > 0)
  return arr[mid-1];

 return arr[mid] < arr[mid-1] ? MinElement(arr,mid+1, high) : MinElement(arr,low,mid-1);
}

int main()
{
int arr[6] = { 3, 2, 1, 6, 5, 4 };

cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr[0]));

return 0;
}

Recursive Solution, which can find min Element even if the array is roated Either Clockwise or Anticlock wise.

Complexity : O(n log n)

# include <iostream>

int MIN(int a, int b)
{
 return a>b?b:a;
}

int MIN(int a,int b,int c){
int min = 0;
if(a>b)
 min = b;
else
 min =a;
 
if(min >c)
return min;
else
return c;

}

using namespace std;

int MinElement(int *arr, int low, int high)
{
 int mid, min, min1;
 
 if(low >= high)
  return -1;

 mid = (low + high)/2;

if(arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1])
 return arr[mid];
if(arr[mid] > arr[mid-1] && arr[mid-1] < arr[mid+1])
return MinElement(arr,low,mid);
else
return MinElement(arr,mid,high);

}

int main()
{
//int arr[6] = { 3, 2, 1, 6, 5, 4 };
int arr[9] = {4, 5, 8, 9, 11, 0, 1, 3, 2};
cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr[0]));

return 0;
}

find_min(A, l, r) {
mid = (l+r)/2;

int min_index;
int mid_left = mid - 1;
int mid_right = mid + 1;

if (l == r) {
return A[l];
} else if (r-l == 1) {
if (A[r] < A[l])
return A[r]
else
return A[l];
}
while (A[mid_left] == A[m] && mid_left > l) {
mid_left --;
}

while (A[mid_right] == A[m] && mid_right > r) {
mid_right ++;
}

if (A[mid_left] >= A[mid] && A[mid] <= A[mid_right])
return A[mid]
else
if (A[mid_left] < A[mid_right])
find_min(A, l , mid_left);
else
find_min(A, mid_right, r);
}

public void do_findMinRotDupAry() {
int a[] = {5, 6, 8, 9, 11, -1, 0, 2, 3};
// int a[] = { 3, 1, 2, 2, 2};
// int a[] = { 3, 2, 0, 6, 5, 4, 4};
// int a[] = { -1, 0, 1, 2, 3,4, 4};
int x = a[0];
for(int i=1; i<a.length; i++) {
x = Math.min(x,a[i]);
}
System.out.println(" a[] " + Arrays.toString(a) + " min dup cir ary = " + x);
}

public class SortedButRotted {
	//sorted but rotted means, sorted elements but rotted by one or two places
	public static void main(String args[]){
	int arr[]={ 4, 4, 5, 5, 5, 6, 1, 1, 2, 2, 3, 3, 3};
	int a=0;
	
	System.out.println(4>=5);
	for(a=0; a<arr.length-1;a++){
		if(arr[a]<=arr[a+1]){
			continue;
		}else{
			break;
		}
	}
	if(a !=(arr.length-1))
		System.out.println("pivot--"+arr[a+1]);
	}

}

int arr [] = {4, 5, 6, -1, -1, 2, 3};
int l = 0;
int r = n-1; //n is size of array
while(l<=r)
{
if(arr[i] > arr[r])
{
l++; r--;
}
else
return arr[l];
}

public class sortedRotated {
	public static void main(String args[]){
		int[] arr = {4, 4, 5, 5, 5, 6, 1, 1, 2, 2, 3, 3, 3};
		minSortedRotated(arr);
		
	}
	public static void minSortedRotated(int[] arr){
		int min=0;
		int i=0;
		//if the array is ascending
		while(arr[i]<=arr[i+1] && i != arr.length-2){
			min = arr[i];
			i++;
		}
		//if the array is descending
		while(arr[i]>=arr[i+1] && i != arr.length-2){
			min = arr[i+1];
			i++;
		}
		//Unrotated
		if(min == 0){
			System.out.println("Array is not rotated");
		}
		else{
			System.out.println("Min is " + min);
		}
	}
}

There are to cases which we have to handle:
1) If array is sorted in ascending order then
we have to find the first point at which left side of the array is smaller then right side.
2) If array is sorted in descending order then
we have to find the first point at which right side of the array is smaller then left side.
Choose the min value from 1 and 2
Code:

public static void main(String[] args) {
        // int[] arr = { 4, 4, 5, 5, 5, 6, 1, 1, 2, 2, 3, 3, 3 };
        int[] arr = { 3, 2, 1, 6, 5, 4 };
        int l = 0;
        int r = arr.length - 1;
        while (arr[l] > arr[r]) {
            int m = l + (r - l) / 2;
            if (arr[m] > arr[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        int minAcs = arr[l];
        l = 0;
        r = arr.length - 1;
        while (arr[r] > arr[l]) {
            int m = (l + (r - l) / 2) + 1;
            if (arr[m] > arr[l]) {
                r = m - 1;
            } else {
                l = m;
            }
        }
        System.out.println("value: " + Math.min(minAcs, arr[r]));
    }

O(log n)