Basic Solution:
Approach:
- The idea is to find the pivot point, divide the array in two sub-arrays and perform binary search.
- The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.
- Using the above statement and binary search pivot can be found.
- After the pivot is found out divide the array in two sub-arrays.
- Now the individual sub – arrays are sorted so the element can be searched using Binary Search.
Implementation:
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.
Below is the implementation of the above approach:
- C++
/* C++ Program to search an element
`` in a sorted and pivoted array*/
#include <bits/stdc++.h>
using namespace std;
/* Standard Binary Search function*/
int binarySearch( int arr[], int low,
`` int high, int key)
{
`` if (high < low)
`` return -1;
`` int mid = (low + high) / 2; /*low + (high - low)/2;*/
`` if (key == arr[mid])
`` return mid;
`` if (key > arr[mid])
`` return binarySearch(arr, (mid + 1), high, key);
`` // else
`` return binarySearch(arr, low, (mid - 1), key);
}
/* Function to get pivot. For array 3, 4, 5, 6, 1, 2
`` it returns 3 (index of 6) */
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);
}
/* Searches an element key in a pivoted
`` sorted array arr[] of size n */
int pivotedBinarySearch( int arr[], int n, int key)
{
`` int pivot = findPivot(arr, 0, n - 1);
`` // If we didn't find a pivot,
`` // then array is not rotated at all
`` if (pivot == -1)
`` return binarySearch(arr, 0, n - 1, key);
`` // If we found a pivot, then first compare with pivot
`` // and then search in two subarrays around pivot
`` if (arr[pivot] == key)
`` return pivot;
`` if (arr[0] <= key)
`` return binarySearch(arr, 0, pivot - 1, key);
`` return binarySearch(arr, pivot + 1, n - 1, key);
}
/* Driver program to check above functions */
int main()
{
`` // Let us search 3 in below array
`` int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
`` int n = sizeof (arr1) / sizeof (arr1[0]);
`` int key = 3;
`` // Function calling
`` cout << "Index of the element is : "
`` << pivotedBinarySearch(arr1, n, key);
`` return 0;
}
Output:
Index of the element is : 8
Complexity Analysis:
-
Time Complexity: O(log n).
Binary Search requires log n comparisons to find the element. So time complexity is O(log n). - Space Complexity: O(1), No extra space is required.