Search in Rotated Sorted Array

Given a sorted (in ascending order) and rotated array arr of distinct elements which may be rotated at some point and given an element key, the task is to find the index of the given element key in the array arr. The whole array arr is given as the range to search.

Rotation shifts elements of the array by a certain number of positions, with elements that fall off one end reappearing at the other end.

Note:- 0-based indexing is followed & returns -1 if the key is not present.

Examples :

Input: arr[] = [5, 6, 7, 8, 9, 10, 1, 2, 3], key = 10
Output: 5
Explanation: 10 is found at index 5.

Input: arr[] = [3, 5, 1, 2], key = 6
Output: -1
Explanation: There is no element that has value 6.

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

Constraints:
1 ≤ arr.size() ≤ 10⁶
0 ≤ arr[i] ≤ 10⁶
1 ≤ key ≤ 10⁵

Approach 01

class Solution {
  public:
    int search(vector<int>& arr, int key) {
        for(int i =0;i < arr.size();i++){
            if(arr[i]==key){
                return i;
            }
        }
        return -1;
    }
};

class Solution:
    def search(self,arr,key):
        n = len(arr)
        for i in range(n):
            if(arr[i] == key):
                return i
        return -1

Time Complexity

• Traversal:
  • The loop iterates through the array to search for the key.
  • In the worst case, the key is at the last position or not present at all, so the loop runs for all \(n\) elements.
  • Hence, the time complexity is \(O(n)\), where \(n\) is the size of the array.
• Comparison:
  • Each element is compared once, and comparisons are \(O(1)\).
• Overall Time Complexity:

  The total time complexity is \(O(n)\), dominated by the traversal step.

Space Complexity

• Array:
  • The input array arr is provided as an argument, and no additional space is allocated for it.
• Other Variables:
  • Variables like i and key use \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(1)\), as no extra data structures are used.

Approach 02:

class Solution {
  public:
    int search(vector<int>& arr, int key) {
        int low = 0, high = arr.size() - 1;

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

            // Check if mid is the key
            if (arr[mid] == key) {
                return mid;
            }

            // Determine the sorted half
            if (arr[low] <= arr[mid]) { // Left half is sorted
                if (key >= arr[low] && key < arr[mid]) {
                    high = mid - 1; // Search in the left half
                } else {
                    low = mid + 1; // Search in the right half
                }
            } else { // Right half is sorted
                if (key > arr[mid] && key <= arr[high]) {
                    low = mid + 1; // Search in the right half
                } else {
                    high = mid - 1; // Search in the left half
                }
            }
        }

        return -1; // Key not found
    }
};

class Solution:
    def search(self,arr,key):
        low = 0
        high = len(arr)-1
        
        while(low<=high):
            mid = low + (high - low)//2
            
            if(arr[mid] == key):
                return mid
                
            if(arr[low] <= arr[mid]):
                if(key < arr[mid] and key >= arr[low]):
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                if(key > arr[mid] and key <= arr[high]):
                    low = mid + 1
                else:
                    high = mid - 1
        return -1

Time Complexity

• Binary Search:
  • Each iteration of the while loop eliminates half of the remaining elements.
  • The maximum number of iterations is \( \log_2(n) \), where \(n\) is the size of the array.
• Key Comparison:
  • Each comparison inside the loop is \(O(1)\).
• Overall Time Complexity:

  The total time complexity is \(O(\log n)\), dominated by the binary search steps.

Space Complexity

• Input Array:
  • The input array arr is provided as an argument, and no additional space is allocated for it.
• Other Variables:
  • Variables like low, high, mid, and key use \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(1)\), as no extra data structures are used.