CareerCup

public static int FindMinInRSA(int[] arr, int start, int end)
        {
            if (start == end)
                return arr[start];

            if (arr[start] < arr[end])
                return arr[start];

            int middle = (start + end) / 2;

            int small1 = (arr[start] < arr[middle] ? arr[start] : arr[middle]);
            int small2 = (arr[middle + 1] < arr[end] ? arr[middle + 1] : arr[end]);

            if (small1 < small2)
                return FindMinInRSA(arr, start, middle);
            else
                return FindMinInRSA(arr, middle + 1, end);
        }

Given a rotated array that was sorted,
say for example
6,7,1,2,3,4,5
use :

{{
for (i = 0; i < n - 1; i ++)
{
if (a[i+1]<a[i])
break;
}
cout<<"Minimum element is at index"<<i<<" and it's value is"<<a[i];
}}


Time complexity is O(n)

Just use bisection and compare to the values at both ends of the array, it is in the book.

public class MinTest {
    public int findMinOfTwoNumbers(int i, int j)
	{
	    if(i<j)
		   return i;
		else
		   return j;
	}
	
	public void findMin(int[] rsa)
	{
	    int length = rsa.length;
		
		if (length == 0)
		{
		    System.out.println("ERR: 1 Rotated sorted array is empty");
			return;
		}
		
		if (length == 1)
		{
		    System.out.println("The minimum is " + rsa[0]);
			return;
		}
		int min = rsa[0];		
		int i = 0;
		for (i = 0; i < length/2; i++)
		{
		   if (rsa[i] < rsa[length-1-i])
		      min = findMinOfTwoNumbers(min, rsa[i]);
		   else
		      min = findMinOfTwoNumbers(min, rsa[length-1-i]);
		}
		
		if ((length%2) != 0)
		   min = findMinOfTwoNumbers(min, rsa[i]);
		   
		System.out.println("The minimum is " + min);
	}
	
	public static void main(String[] args)
	{
	    MinTest m = new MinTest();
		int [][] testArray = {{},
		                      {1},
							  {1,2},
							  {2,1},
							  {1,2,3},
							  {3,1,2},
							  {2,3,1},
							  {1,2,3,4},
							  {4,1,2,3},
							  {3,4,1,2},
							  {2,3,4,1},
							  {1,1,1,1,1},
		                      {-1},
							  {-1,-2},
							  {-2,-1},
							  {-1,-2,-3},
							  {-3,-1,-2},
							  {-2,-3,-1},
							  {-1,-2,-3,-4},
							  {-4,-1,-2,-3},
							  {-3,-4,-1,-2},
							  {-2,-3,-4,-1},
							  {-1,-1,-1,-1,-1}};
		
		int length = testArray.length;
		
		for(int i = 0; i < length;  i++)
		    m.findMin(testArray[i]);
	}
}

#include<iostream>
#include<set>
using namespace std;
set<int> myset;
void binarysearch(int a[],int n)
{
int l=0,mid;
int h=n-1;
while(a[l]>a[h])
{
mid=(l+h)/2;
if(a[mid]>a[h])
l=mid+1;
else
h=mid;
}
myset.insert(a[1]);
myset.insert(a[l]);
set<int> :: iterator it=myset.begin();
cout<<"the minimum element is "<<*it<<endl;
cout<<"the rotation is "<<l<<endl;

}
int main()
{
int a[100];
cout<<"enter the elements";
cout<<endl;
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
binarysearch(a,n);
}

// O(log n) steps 
int min (int array[], int left, int right) {
    int middle = (left + right)/2;
    int temp;
    if (issorted(array, left, middle) 
        && issorted(array, middle + 1, right)) {
        return ((array[left] < array[middle+1]) ? array[left] : array[middle + 1]);
    } else if (issorted(array, left, middle)) {
        temp = min (array, middle+1, right);
        return ((array[left] < temp) ? array[left] : temp );
    } else if (issorted(array, middle+1, right)) {
        temp = min (array, left, middle);
        return ((array[middle+1] < temp) ? array[middle+1] : temp); 
    }
}


int issorted (int array[], int left, right) {
    if (array[left] < array[right])
        return 1;
    else 
        return 0;    
}

even though array contains duplicates we can use divide and conquer by little modification

A simple modified binary search would work...

#include<iostream>
using namespace std;
int Min(int arr[],int size);
int main()
{
	int arr[] = {4,5,6,7,8,9,1,2,3};
	int size = sizeof(arr)/sizeof(arr[0]);
	cout<<Min(arr,size);
	return 0;
}
int Min(int arr[],int size)
{
	if(size==1) return arr[0];
	
	int l = 0,h = size-1,m;
	while(l<h)
	{
		if(l+1 == h) return min (arr[l],arr[h]);
		m = l + (h-l)/2;
		if(arr[l]>arr[m]) h = m;
		else if(arr[l]<arr[m]) l = m;
		else return arr[m];
	}
}

void findMin(int a[]){
		for(int i=0;i<a.length;i++){
			if(a[i]-a[i+1]>0){
				System.out.print("Min Elem of Arr::"+a[i+1]);
				break;
			}
		}
	}

public int searchMin(int[] array, int s, int f){        
        if(s == f)
            return array[s];
        else if(s - f == 1)
            return (array[s] < array[f]? array[s]: array[f]);
        else{
            int mid = (f - s)/2 + s;  
            if(array[mid] < array[mid - 1])
                return array[mid];
            else if(array[mid] < array[s])
                return searchMin(array, s, mid - 1);
            else if(array[f] < array[mid])
                return searchMin(array, mid + 1, f);
            else
                return array[s];
        }   
}

int minIndex (int *arr, int size)
{
        int low = 0;
        int mid = (size/2);
        int high = size-1;

        while (low<high)
        {
                if (arr[mid] > arr[mid+1])
                        return mid+1;
                if (arr[mid-1] > arr[mid])
                        return mid;
                if (arr[low] < arr[high])
                        return low;
                if (arr[low] < arr[mid])
                {
                        low = mid+1;
                }
                else if (arr[low] > arr[mid])
                {
                        high = mid-1;
                }
                mid = low + (high-low)/2;
        }
}

public static int findNumOfShifts2(int [] A){
	int start=0;
	int end=A.length-1; 
	while(start<end){
		int mid = start + (end-start)/2;
		if(A[start]>A[start+1])
			break;
		
		if(A[mid]<A[start])
			end=mid;
		else if (A[mid]>A[end])
			start=mid;
		else 
			start=start+1;//fallback to linear search
	}
	return A[(start+1)%A.length]; 
}

Test with:
Input:
{1, 2, 2, 2, 2, 2, 2, 2, 2}

For this input, try to rotate 0, 1, 2, ..., the above code output the correct result, which is 1.

My solution in C++ below.

As mentioned in the question, it's better to write (start + end) / 2 = start + (end - start) / 2 as it doesn't imply an addition of two integers which results could be greater than INT_MAX.

#include <iostream>
#include <vector>

using namespace std;

int findMin(vector<int> L) {
    if (L.size() == 0) {
        // Not supported
    }
    if (L.size() == 1)
        return L[0];
    int start = 0, end = L.size() - 1, middle;
    while ((middle = start + (end - start) / 2) != start) {
        if (L[middle] > L[end]) {
            start = middle;
        } else if (L[start] > L[middle]) {
            end = middle;
        } else {
            // Error, the list is not correct
        }        // At this point, L[start] > L[end]
    }
    return L[end];
}

It can be done pretty straightforward. We're basically looking for the point of rotation and the beautiful thing about this case is that one part of the array will always be sorted, given distinct elements.
So we just check if the latter part of the array is sorted, if it's not, we look for the inflection point there and hence the min. If it is, that means that either the inflection point is in the lower part of the array or maybe there's no inflection point at all.

int getMinimum(vector<int> input){
	if(!input.size())
		return -1;
	if(input.size()==1){
		return input[0];
	}

	int start = 0;
	int end = input.size()-1;
	int mid;
	while(start <= end){
		mid = start + (end-start)/2;
		if(start==end){
			return input[start];
		}

		if(input[mid] > input[end]){
			start = mid+1;
		} else {
			end = mid;
		}
	}
}

The point at which rotation has occurred can be found only in linear time. So the entire thing will take O(n), the same as finding min in any array.

My code is below with the algorithm as comments. Works even for the repeated elements.

//Find Min in Rotated Sorted Array
//Example: int array[10] = {7, 8, 9, 10, 11, 12, 3, 4, 5, 6};
// Min in the above array is 3
// Solution: Recursively search (Modified binary search) for the Pivot where is the smallest Element is present
// Algorithm: 
// 1) Find the Mid of the Array 
// 2) call the recursive function on segment of array in which there is a deviation in the order
// If (A[low] > A[mid]) array segment in which deviation in the order present is (low, mid)
// If (A[low] < A[mid]) array segment in which deviation in the order present is (mid + 1, high) 
// Time Complexity: O(logn)
// Space Complexity: is of the recursive function stack that is being used

#define MIN(x,y) (x) <= (y) ? (x): (y)

int MininRotatedSortedArray(int A[], int low, int high)
{
    if(low > high)
        return -1;

    if(low == high - 1)
        return MIN(A[low], A[high]);

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

    if(A[low] > A[mid])
        return MininRotatedSortedArray(A, low, mid);
    else if(A[low] < A[mid])
        return MininRotatedSortedArray(A, mid + 1, high);
    else
        return A[mid];
}