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.
Logic:
- 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
Explanation:
Program:
/*Search an element in a sorted and rotated array*/ #include<stdio.h> /*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); else 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; else { if(arr[0] <= elementToFind) Index = binarySearch(arr,0,pivot - 1,elementToFind); else Index = binarySearch(arr,pivot + 1,size - 1,elementToFind); } if(Index == -1) printf("Key element not found\n"); else printf("Key element index:%d\n",Index); }