Posted By

jaircazarin on 10/09/08


Tagged

Algorithms Microsoft-Interview


Versions (?)

Who likes this?

3 people have marked this snippet as a favorite

jaircazarin
sergeizen
skammer


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.

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. int FindSortedArrayRotationRecursive(int *array, int start, int end)
  5. {
  6. if(start == (end-1))
  7. return start+1;
  8. if(array[start] <= array[end-1])
  9. return 0;
  10. int middle = (start + end)/2;
  11. if(array[start] > array[middle])
  12. return FindSortedArrayRotationRecursive(array, start, middle);
  13. else
  14. return FindSortedArrayRotationRecursive(array, middle, end);
  15. }
  16.  
  17. int FindSortedArrayRotationIterative(int *array, int length)
  18. {
  19. int start = 0;
  20. int end = length-1;
  21. if(array[start] < array [end])
  22. return start;
  23. while(start != end)
  24. {
  25. int middle = (start+end)/2;
  26. if(array[start] < array[middle])
  27. start = middle;
  28. else
  29. end = middle;
  30. }
  31. return start+1;
  32. }
  33.  
  34. int main()
  35. {
  36. int array[] = { 8, 9, 10, 1, 2, 3, 4, 5, 6, 7};
  37. int x = FindSortedArrayRotationRecursive(array, 0, 10);
  38. int y = FindSortedArrayRotationIterative(array, 10);
  39. printf("%d\n", x);
  40. printf("%d\n", y);
  41. }

Report this snippet  

You need to login to post a comment.