Searching: Given an sorted rotated array, find the given key is present

Problem Statement:

You are given a sorted and rotated array and a key.

You need to find if the index of the key.

Example:

Input:

arr = [3, 4, 5, 1, 2] k = 2

Output: 4

Solution 1: Brute force approach

In this approach, we will go through the whole array to check if the element is present or not and then return the result.

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Efficient approach

In this approach, we will use binary search to get the result.

Time Complexity: O(log n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

int solution_1(vector<int>& arr, int key) 
{

    for (int i = 0; i < arr.size(); i++) 
    {
        if (arr[i] == key)
            return i;
    }

    return -1;
}


int solution_2(vector<int>& arr, int key) 
{
  
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high) 
    {
        int mid = low + (high - low) / 2;

        if (arr[mid] == key)
            return mid;

        if (arr[mid] >= arr[low]) 
        {
          
            if (key >= arr[low] && key < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }

        else 
        {
          
            if (key > arr[mid] && key <= arr[high])
                low = mid + 1;

            else
                high = mid - 1;
        }
    }
	

    return -1; 
}

int main() {

    vector<int> arr = {3, 4, 5, 1, 2};
    int key = 2;

    int result = solution_1(arr, key);

    cout << "Solution 1 = "<< result << endl ;

    result = solution_2(arr, key);

    cout << "Solution 2 = "<< result << endl ; 
        
    return 0 ;
}

Output

Solution 1 = 4
Solution 2 = 4