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);
}
