Search an element in a sorted and rotated array

Search an element in a sorted and rotated array

Search an element in a sorted and rotated array

Search an element in a sorted and rotated array in ascending order. For example, 1 2 3 4 5 might become 3 4 5 1 2.




  • The basic idea is to find the pivot point, which is the only element has smaller element to its next
  • Divide the array into two sub-arrays using pivot point and perform a binary search operation.
  • Finding pivot Point:
    – Find the middle element of the array
    – Check mid element is smaller than its left element, if yes mid – 1 is the pivot
    – if no Check mid element is greater than its right element, if yes mid is the pivot
    – if no Check mid element is less than first element, repeat above steps with first half
    – Otherwise repeat above steps with Second half
  • Finally will get the pivot element
  • Check the pivot element is key element
  • Else check the pivot element is less than or equal to first element in the array, proceed for binary search operation for first half of the array
  • Otherwise check with second half of the array



/*Search an element in a sorted and rotated array*/


/*To find pivot point */
int findPivot(int arr[],int start,int end)
             int mid;
             if (start > end)
                    return -1;
             if(start == end)
                    return end;
             mid = (start + end) / 2;
             if(arr[mid] < arr[mid - 1])
                    return(mid - 1);
             if(arr[mid] > arr[mid + 1])
                    return mid;
             if(arr[start] >= arr[mid])
                    return findPivot(arr,start,mid - 1);
             return findPivot(arr,mid + 1,end);

/*To find a element in array using binary search*/
int binarySearch(int arr[],int start,int end,int elementToFind)
            int mid;
            if (start > end)
                   return -1;
            mid = (start + end) / 2;
            if(elementToFind == arr[mid])
                   return mid;
            if(arr[mid] < elementToFind)
                   return binarySearch(arr,mid + 1,end,elementToFind);
                   return binarySearch(arr,start,mid - 1,elementToFind);


void main()
           int arr[]={16,72,100,104,4,8,15};
           int size = sizeof(arr) / sizeof(arr[0]);
           int pivot;
           int elementToFind = 100;
           int Index;

           pivot = findPivot(arr,0,size);

           if(arr[pivot] == elementToFind)
                   Index = pivot;
                   if(arr[0] <= elementToFind)
                            Index = binarySearch(arr,0,pivot - 1,elementToFind);
                            Index = binarySearch(arr,pivot + 1,size - 1,elementToFind);
          if(Index == -1)
                   printf("Key element not found\n");
                   printf("Key element index:%d\n",Index);

You Might also like:

         Find the Insert Position in Sorted Array

Know about binary Search: Binary Search

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link


A Computer Science graduate who likes to make things simpler. When he’s not working, you can find him surfing the web, learning facts, tricks and life hacks. He also enjoys movies in his leisure time.
5 1 vote
Article Rating
Notify of
Inline Feedbacks
View all comments
Would love your thoughts, please comment.x