# 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

## 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)
else
printf("Key element index:%d\n",Index);
}
```

## Find the Insert Position in Sorted Array

### Vignesh

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
Subscribe
Notify of