Search element in sorted and rotated array
Problem
Rotate an array in ascending order at some pivot which is unknown to you beforehand,
- Find pivot in that array
- Search for the given element in that array
Algorithm
Implementation
int findPivot(int arr[], int low, int high)
{
// base cases
if (high < low) return -1;
if (high == low) return low;
int mid = (low + high)/2; /*low + (high - low)/2;*/
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid-1);
if (arr[low] >= arr[mid])
return findPivot(arr, low, mid-1);
return findPivot(arr, mid + 1, high);
}
// Returns index of key in arr[l..h] if key is present,
// otherwise returns -1
int search(int arr[], int l, int h, int key)
{
if (l > h) return -1;
int mid = (l+h)/2;
if (arr[mid] == key) return mid;
/* If arr[l...mid] is sorted */
if (arr[l] <= arr[mid])
{
/* As this subarray is sorted, we can quickly
check if key lies in half or other half */
if (key >= arr[l] && key <= arr[mid])
return search(arr, l, mid-1, key);
return search(arr, mid+1, h, key);
}
/* If arr[l..mid] is not sorted, then arr[mid... r]
must be sorted*/
if (key >= arr[mid] && key <= arr[h])
return search(arr, mid+1, h, key);
return search(arr, l, mid-1, key);
}