## Posted By

jaircazarin on 10/09/08

## Who likes this?

3 people have marked this snippet as a favorite

# Find Sorted Array Rotation

/ Published in: C

Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.

Consider performance, memory utilization and code clarity and elegance of the solution when implementing the function.

`#include<stdio.h>#include<stdlib.h> int FindSortedArrayRotationRecursive(int *array, int start, int end){	if(start == (end-1))		return start+1;	if(array[start] <= array[end-1])		return 0;	int middle = (start + end)/2;	if(array[start] > array[middle])		return FindSortedArrayRotationRecursive(array, start, middle);	else		return FindSortedArrayRotationRecursive(array, middle, end);} int FindSortedArrayRotationIterative(int *array, int length){    int start = 0;	int end = length-1;	if(array[start] < array [end])		return start;		while(start != end)	{		int middle = (start+end)/2;		if(array[start] < array[middle])			start = middle;		else			end = middle;	}	return start+1;} int main(){    int array[] = { 8, 9, 10, 1, 2, 3, 4, 5, 6, 7};    int x = FindSortedArrayRotationRecursive(array, 0, 10);    int y = FindSortedArrayRotationIterative(array, 10);    printf("%d\n", x);    printf("%d\n", y);}`