« Search an element in a sorted and rotated Array

Search an element in a sorted and rotated Array

Given a sorted and rotated array arr[] of size N and a key, the task is to find the key in the array.

Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}, key = 3

Output : Found at index 8

Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}, key = 30

Output : Not found

Input : arr[] = {30, 40, 50, 10, 20}, key = 10

Output : Found at index 3

Follow the steps mentioned below to implement the idea:

• Use a recursive function to implement binary search to find the key:
• Find middle-point mid = (l + h)/2
• If the key is present at the middle point, return mid.
• Else if the value at l is less than the one at mid then arr[l . . . mid] is sorted If the key to be searched lies in the range from arr[l] to arr[mid], recur for arr[l . . . mid].

• Else recur for arr[mid+1 . . . h]
  Else arr[mid+1. . . h] is sorted: If the key to be searched lies in the range from arr[mid+1] to arr[h], recur for arr[mid+1. . . h]. Else recur for arr[l. . . mid]

Copy
1#include<iostream>
2#include<iomanip>
3#include<algorithm>
4#include<string>
5#include<cstring>
6#include<vector>
7#include<cmath>
8#include <map>
9#include<climits>
10//climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int search(int *arr, int l, int r, int key){
15    if(l > r){
16        return -1;
17    }
18
19    int mid = (l + r) / 2;
20
21    if(arr[mid] == key){
22        return mid;
23    }
24
25    if (arr[l] <= arr[mid]) {
26        if (key >= arr[l] && key <= arr[mid]){
27            return search(arr, l, mid - 1, key);
28        }
29
30        return search(arr, mid + 1, r, key);
31    }
32    if (key >= arr[mid] && key <= arr[r]){
33        return search(arr, mid + 1, r, key);
34    }
35
36    return search(arr, l, mid - 1, key);
37}
38int main()
39{
40    int arr[] = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
41    int n = sizeof(arr);
42    int key = 6;
43    int i = search(arr, 0, n - 1, key);
44
45    if (i != -1){
46        cout << "Index: " << i << endl;
47    }else{
48        cout << "Key not found";
49    }
50
51    return 0;
52}