ashish
BAN USERThe 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;
}
Solution: Sort -- O(nlogn), Find Pair in Sorted Array -- O(n)
- ashish October 17, 2012