2

First let me say that I am new to C so my approach is basic. I am attempting to check a sorted array for a point where it was rotated. For example (1 2 4 5 9) becomes (5 9 1 2 4). I am attempting to "split" the array into two sub arrays and check one starting from [0] and increasing by one and one starting from [4] and decreasing by one. Here is what I have so far:

#define size 5
int main(void)
{
int x, i, j, start, end;
int array1[size]= {4, 8, 0, 1, 3};
start = 0;
end = size -1;
while(start < end)
{
if (array1[start] < array1[end])
    start++;
    end--;

I guess some of the questions I am having is if my approach is good (outside to inside) or if I should start in the middle and work my way out. Also how would I code the determination for where the pivot actually happens. I see a few answers for C++ in SO however I am not seeing many that are clear for C so I figured I'd ask. Any advice is appreciated.

3
  • That loop would continue indefinitely since array1[0] == 4 and array1[end] == 3 and if (4 < 3) would not take the branch.
    – obataku
    Sep 15, 2012 at 7:01
  • May I suggest that you try it in the compiler? Not to see if it is the best solution, or if it is correct for all cases, but to see if there are some obvious errors that the compiler will help you catch. Sep 15, 2012 at 7:03
  • @bardockyo start and end will never change so the loop will continue indefinitely.
    – obataku
    Sep 15, 2012 at 7:07

2 Answers 2

2

Code for finding pivot element in C

int findPivot(int arr[], int low, int high)
{
   // base cases
   if (high < low)  return -1;
   if (high == low) return low;

   int mid = (low + high)/2;   /*low + (high - low)/2;*/
   if (mid < high && arr[mid] > arr[mid + 1])
     return mid;
   if (mid > low && arr[mid] < arr[mid - 1])
     return (mid-1);
   if (arr[low] >= arr[mid])
     return findPivot(arr, low, mid-1);
   else
     return findPivot(arr, mid + 1, high);
}

where you return -1 when array is already sorted, rest of the things as usual like a binary search

1

The problem is rather trivial to solve. Since the original set is sorted, just iterate forward until the element you hit is less than the final element in the array -- this was the original first element, so you know that its distance from the start is congruent to R (mod N) where R is the rotation distance and N is size.

int last = array[size - 1];
int r;
for (r = 0; array[r] >= last; ++r) ;
int pivot = array[r];
/* pivot was the original array[0] */
2
  • 5
    This is O(n), but there is a way to do that in O(log(n))
    – Antoine
    Oct 8, 2012 at 18:37
  • O(log(n)) , can be achieved using the concept of Binary Search. Jun 13, 2017 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.