CareerCup

PIVOT IS THE ELEMENT WHICH IS LESSER THEN IN LEFT ELEMENT AND RIGHT ELEMENT AS WELL.. so we need to use that...and recurse..where as problem will be divided in three parts when we have one element left then it is the pivot and when we are left with 2 elements then minimum of that...and when of more then three then we need to check the above stated condition and accordingly move to left or right part

use binary search O(logn)

I confess I had to go look up what a rotated array was, but I'm not sure what you mean by the pivot. Is it the "first" element in the sort? If so, it seems like all you'd need to do is iterate through each element in the array, comparing it to the previous element (or the last element in the array when checking the first element) until you found the one element that had a lower sort value than its predecessor.

Pivot is first element of array

void main() {
	
	int a[20],n,i;
	scanf("%d",&n);
	for (i = 0; i<n; i++)
		scanf("%d",&a[i]);
	int last = a[n-1];//last element
	for(i = 0; a[i]>=last;i++);

	printf("\n%d %d",i,a[i]);

}

The following code will work only when all the elements are unique (It works otherwise too but it'll break in certain conditions). The following code also assumes that the sorted array has been rotated i.e. there exists a pivot.

#include <iostream>
using namespace std;

int getPivot( int* arr, int N ) {
  if ( NULL == arr ) {
    return -1;
  }

  int low = 0;
  int high = N - 1;
  int mid;
  int last = arr[N - 1];
  
  while ( low <= high ) {
    mid = ( low + high ) / 2;
    cout << "Mid: " << mid << endl;
    if ( arr[mid] < last ) {
      high = mid - 1;
    } else {
      if ( mid < N - 1 && arr[mid] > arr[mid + 1] ) {
        return mid;
      }
      low = mid + 1;
    }
  }

  return mid;
}

void display( int *arr, int N ) {
  if ( NULL == arr ) {
    return;
  }

  for ( int i = 0; i < N; i++ ) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}

void rotateByOne( int *arr, int N ) {
  if ( arr == NULL ) {
    return;
  }

  int last = arr[N - 1];
  for ( int i = N-1; i > 0; i-- ) {
    arr[i] = arr[i - 1];
  }

  arr[0] = last;
}
  

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

  int pivot;
  for ( int i = 0; i <= N; i++ ) {
    cout << "=====================================" << endl;
    display( arr, N );
    pivot = getPivot( arr, N );
    cout << "Pivot: " << pivot << endl;
    rotateByOne( arr, N );
  }

  return 0;
}

pivot element will always be smaller then its left and right elemnets.so if middle element is smaller then the 1st element of the subarray, traverse left, else if midle element is greater then the first, traverse right.also when only one element left, thats the pivot

public static void FindPivotInrotatedSortedArray(int[] a)
{
if (a.Length == 0)
return;
if (a.Length == 1)
{
Console.WriteLine("Pivot is: {0}", a[0]);
return;
}
for (int i = 0; i < a.Length; i++)
{
if (i == 0)
{
if (a[i] < a[i + 1] && a[i] < a[a.Length - 1])
{
Console.WriteLine("Pivot is: {0}", a[i]);
break;
}
}
else if (i == a.Length - 1)
{
if (a[i] < a[0] && a[i] < a[i - 1])
{
Console.WriteLine("Pivot is: {0}", a[i]);
break;
}
}
else
{
if (a[i] < a[i + 1] && a[i] < a[i - 1])
{
Console.WriteLine("Pivot is: {0}", a[i]);
break;
}
}
}
return;


}