Revision: 8825
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at October 9, 2008 17:26 by jaircazarin
Initial Code
#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);
}
Initial URL
Initial Description
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.
Initial Title
Find Sorted Array Rotation
Initial Tags
Initial Language
C