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.