Improved Solution:
Approach: Instead of two or more pass of binary search the result can be found in one pass of binary search. The binary search needs to be modified to perform the search. The idea is to create a recursive function that takes l and r as range in input and the key.
- Find middle point mid = (l + h)/2 2) If key is present at middle point, return mid. 3) Else If arr[l…mid] is sorted a) If key to be searched lies in range from arr[l] to arr[mid], recur for arr[l…mid]. b) Else recur for arr[mid+1…h] 4) Else (arr[mid+1…h] must be sorted) a) If key to be searched lies in range from arr[mid+1] to arr[h], recur for arr[mid+1…h]. b) Else recur for arr[l…mid]
Below is the implementation of above idea:
// Search an element in sorted and rotated
// array using single pass of Binary Search
#include <bits/stdc++.h>
using namespace std;
// 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);
`` /*If key not lies in first half subarray,
`` Divide other half into two subarrays,
`` such that we can quickly check if key lies
`` in other half */
`` return search(arr, mid + 1, h, key);
`` }
`` /* If arr[l..mid] first subarray is not sorted, then arr[mid... h]
`` must be sorted subarray */
`` if (key >= arr[mid] && key <= arr[h])
`` return search(arr, mid + 1, h, key);
`` return search(arr, l, mid - 1, key);
}
// Driver program
int main()
{
`` int arr[] = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
`` int n = sizeof (arr) / sizeof (arr[0]);
`` int key = 6;
`` int i = search(arr, 0, n - 1, key);
`` if (i != -1)
`` cout << "Index: " << i << endl;
`` else
`` cout << "Key not found" ;
}
Output:
Index: 2
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).
As no extra space is required.