Search an Element in a Rotated Sorted Array

Given a rotated sorted array and a target element, find the index of the target element in the array. If the target is not found, return -1. The array is initially sorted in ascending order and then rotated at an unknown pivot.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [4, 5, 6, 7, 0, 1, 2]
target = 0
Output: 4
Explanation: The element 0 is found at index 4.

Example 2:
Input:
arr = [4, 5, 6, 7, 0, 1, 2]
target = 3
Output: -1
Explanation: The element 3 is not found in the array, so the output is -1.

Example 3:
Input:
arr = [1]
target = 1
Output: 0
Explanation: The element 1 is found at index 0.

Approach to search an element in a rotated sorted array

  1. Binary Search with Modifications:
    • Since the array is sorted but rotated, a modified binary search can be used to find the target efficiently.
  2. Determine Sorted Half:
    • For each element at mid, determine which half (left or right) is sorted by comparing arr[left] and arr[mid].
    • If the left half is sorted, check if the target lies within this half; if not, search the right half.
    • If the right half is sorted, check if the target lies within this half; if not, search the left half.
  3. Adjust Search Range:
    • Based on which half is sorted and whether the target lies within the sorted half, adjust the left and right pointers to narrow down the search range.

C++ Program to search an element in a rotated sorted array

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

// Function to search for an element in a rotated sorted array
int searchInRotatedArray(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

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

        // Determine which half is sorted
        if (arr[left] <= arr[mid]) { // Left half is sorted
            if (arr[left] <= target && target < arr[mid]) {
                right = mid - 1; // Target in left half
            } else {
                left = mid + 1;  // Target in right half
            }
        } else { // Right half is sorted
            if (arr[mid] < target && target <= arr[right]) {
                left = mid + 1; // Target in right half
            } else {
                right = mid - 1; // Target in left half
            }
        }
    }

    return -1; // Target not found
}

int main() {
    vector<int> arr = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;
    int result = searchInRotatedArray(arr, target);
    cout << "Index of target element: " << result << endl;
    return 0;
}

Java Program to search an element in a rotated sorted array

java
public class SearchInRotatedArray {

    // Function to search for an element in a rotated sorted array
    public static int searchInRotatedArray(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

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

            // Determine which half is sorted
            if (arr[left] <= arr[mid]) { // Left half is sorted
                if (arr[left] <= target && target < arr[mid]) {
                    right = mid - 1; // Target in left half
                } else {
                    left = mid + 1;  // Target in right half
                }
            } else { // Right half is sorted
                if (arr[mid] < target && target <= arr[right]) {
                    left = mid + 1; // Target in right half
                } else {
                    right = mid - 1; // Target in left half
                }
            }
        }

        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        int result = searchInRotatedArray(arr, target);
        System.out.println("Index of target element: " + result);
    }
}

Python Program to search an element in a rotated sorted array

python
# Function to search for an element in a rotated sorted array
def search_in_rotated_array(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        # Check if mid is the target element
        if arr[mid] == target:
            return mid

        # Determine which half is sorted
        if arr[left] <= arr[mid]: # Left half is sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1 # Target in left half
            else:
                left = mid + 1  # Target in right half
        else: # Right half is sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1 # Target in right half
            else:
                right = mid - 1 # Target in left half

    return -1 # Target not found

# Example usage
if __name__ == "__main__":
    arr = [4, 5, 6, 7, 0, 1, 2]
    target = 0
    result = search_in_rotated_array(arr, target)
    print("Index of target element:", result)

Time Complexity

  • O(log n): The algorithm performs a binary search, which divides the search space in half at each step, resulting in logarithmic time complexity.

Space Complexity

  • O(1): The algorithm uses a constant amount of extra space for variables left, right, and mid.

DSA

3267

211

Related Articles