Search an element in a sorted and pivoted array e.g Array is Rotated by some length K. Now you Have to Search Element in Complexity less then O(N)

Data Structure Used: Array

Hint : Find the pivot point, divide the array in two sub-arrays and call binary search. Thats It :)

Approach to Solve Problem:
Find the pivot point, divide the array in two sub-arrays and call binary search.The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it. Using above criteria and binary search methodology we can get pivot element in O(logn) time

Input arr[] = {3, 4, 5, 1, 2}
Element to Search = 1
1) Find out pivot point and divide the array in two
sub-arrays. (pivot = 2) /*Index of 5*/
2) Now call binary search for one of the two sub-arrays.
(a) If element is greater than 0th element then
search in left array
(b) Else Search in right array
(1 will go in else as 1 < 0th element(3)) 3) If element is found in selected sub-array then return index Else return -1. Efficient Algorithm: 1. A Pivot Point is point around which array is rotated so 1st we need to find out its location/index. lets say it pivot. a. to find pivot point we use same idea of binary search & check if arr[mid]>a[mid+1] if true then return pivot=mid.
b else if arr[low]

int binarySearch(int arr[], int low, int high, int no)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/

if(no == arr[mid])
return mid;
if(no > arr[mid])
return binarySearch(arr, (mid + 1), high, no);
else
return binarySearch(arr, low, (mid -1), no);
}
/*Return -1 if element is not found*/
return -1;
}

/* Function to get pivot. For array 3, 4, 5, 6, 1, 2
it will return 3 e.g. position of pivoted element */
int findPivot(int arr[], int low, int high)
{
int mid = (low + (high-low))/2; /*low + (high - low)/2;*/
if(arr[mid] > arr[mid + 1])
return mid;
if(arr[low] > arr[mid])
return findPivot(arr, low, mid-1);
else
return findPivot(arr, mid + 1, high);
}

/* Searches an element no in a pivoted sorted array arrp[]
of size arr_size */
int pivotedBinarySearch(int arr[], int arr_size, int no)
{
int pivot = findPivot(arr, 0, arr_size-1);
if(arr[pivot] == no)
return pivot;
if(arr[0] <= no)
return binarySearch(arr, 0, pivot-1, no);
else
return binarySearch(arr, pivot+1, arr_size-1, no);
}


int main()
{
int arr[] = {3, 4, 5, 6, 7, 1, 2};
int n = 5;
printf("Index of the element is %d", pivotedBinarySearch(arr, 7, 5));
getchar();
return 0;
}

Time Complexity O(Logn)
Space Complexity O(1)
Run Here https://ideone.com/KMOvG