#include
//find pivot element using binary search.
//Code obtained from http://www.studyalgorithms.com
//Feel free to copy but please acknowledge the site wherever possible
int findPivot(int arr[], int size)
{
if(arr[0] < arr[size-1])
{
//means that the array is not rotated at all.
//the first element is the pivot element
return 0;
}
// setting the first and last for binary search
int start = 0;
int finish = size-1;
int mid;
while(start < finish)
{
mid = start + (finish - start)/2;
if(arr[start] < arr[mid])
{
//means that the first half is sorted completely
//Code obtained from http://www.studyalgorithms.com
//Feel free to copy but please acknowledge the site wherever possible
start = mid;
}
else
{
//means that the second half is sorted completely
finish = mid;
}
}
//as the loop finishes, the variable mid points at the largest element in the array
//so we return the next element as our pivot.
return (mid+1);
}
//iterative binary search which returns index of element
int binarySearchIterative(int arr[], int low, int high, int data)
{
int mid;
while(low<=high)
{
mid = low + (high-low)/2; //To avoid overflow by (low + high)
if(arr[mid] == data)
return mid;
else
{
if(arr[mid] < data)
low = mid + 1; // search in right half
else
high = mid - 1; // search in left half
}
}
return -1;
}
// function to search the element in the array
// returns -1 if the element is not found
int search(int arr[], int size, int data)
{
int pivot = findPivot(arr, size);
int index = -1;
if(pivot == 0)
{
//the array is not rotated at all
//Code obtained from http://www.studyalgorithms.com
//Feel free to copy but please acknowledge the site wherever possible
index = binarySearchIterative(arr, 0, size-1, data);
}
else
{
//if the array was rotated and pivot > 0
if(data >= arr[0])
{
// our element lies in the first half.
index = binarySearchIterative(arr, 0, pivot-1, data);
}
else
{
// our element lies in the second half
index = binarySearchIterative(arr, pivot, size-1, data);
}
}
//return the index of the element
return index;
}
int main(void) {
// your code goes here
int arr[] = {4, 8, 15, 16, 23, 24, 25, 26, 27, 28, 29, 30};
int p = search(arr,12,23);
if(p == -1)
printf("NOT FOUND");
else
printf("p = %d",p);
return 0;
}
//Code obtained from http://www.studyalgorithms.com
//Feel free to copy but please acknowledge the site wherever possible