Advanced Search

Find Sorted Array Rotation

/ Published in: C
Save to your folder(s)
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

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  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


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.