Search an Element in Sorted Rotated Array

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance eBay Expedia Facebook Google Microsoft Nvidia Oracle PayPal Paytm VMware Walmart Labs Zillow
Array Binary SearchViews 1568

In search in sorted rotated array problem we have given a sorted and rotated array and an element, check if the given element is present in the array or not.

Examples

Input
nums[] = {2, 5, 6, 0, 0, 1, 2}
target = 0
Output
true

Search an Element in Sorted Rotated Array

Input
nums[] = {2, 5, 6, 0, 0, 1, 2}
target = 3
Output
false

Naive Approach for Search an Element in Sorted Rotated Array

Linearly traverse in the array and search for the target value.

  1. Run a loop for i = 0 to n(not included), where n is the number of elements in the array.
  2. At every iteration, check if nums[i] equal to a target value or not. If it is equal, return true, else continue for the next element.
  3. If there is no element equals to the target value, return false.

JAVA Code

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target) {
        int n = nums.length;
        // Traverse the given array and search for the target value
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;

        System.out.println(searchTarget(nums, target));

        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target));
    }
}
true
false

C++ Code

#include<bits/stdc++.h> 
using namespace std;

bool searchTarget(int *nums, int target, int n) {
    // Traverse the given array and search for the target value
    for (int i = 0; i < n; i++) {
        if (nums[i] == target)
            return true;
    }
    return false;
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, n)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

Complexity Analysis for Search an Element in Sorted Rotated Array

Time Complexity = O(n)
Space Complexity = O(1) 
where n is the number of elements in the array.

Optimal Approach for Search an Element in Sorted Rotated Array

The array might contain duplicates, so the idea of dividing the array into two sorted arrays will not work.

Let the starting index of the array be l and ending index be h,

  1. Find the mid, as mid = (l + h) / 2.
  2. If arr[mid] equals to target value, return true.
  3. If arr[l] is equals to arr[h] is equals to arr[mid], then increment l and decrement h.
  4. Else if arr[l] is less than or equals to arr[mid], then the left half is sorted, if the target lies in the range of sorted left half, search in the left half else search in the right half.
  5. If the above condition is not true, the right half, from mid to h, is sorted, if the target lies in the range of sorted right half, search in right half else search in the left half.

JAVA Code

public class SearchInRotatedAndSortedArray {
    private static boolean searchTarget(int[] nums, int target, int l, int h) {
        // Index out of bound, element does not exist
        if (l > h)
            return false;
        // Find the middle element
        int mid = (l + h) / 2;
        // If this is the target element, return true
        if (nums[mid] == target) {
            return true;
        }
        // If nums[l] = nums[h] = nums[mid], increment l and decrement h
        if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
            return searchTarget(nums, target, l + 1, h - 1);
        }
        
        // If nums[l] <= nums[mid], left half is sorted
        if (nums[l] <= nums[mid]) {
            // If the target lies in the first half, search in first half
            if (target >= nums[l] && target <= nums[mid]) {
                return searchTarget(nums, target, l, mid - 1);
            }
            // Else search in second half
            return searchTarget(nums, target, mid + 1, h);
        }
        
        // If first half is not sorted, then second half is sorted
        // If the target is present in the second half, search in second half
        if (target >= nums[mid] && target <= nums[h]) {
            return searchTarget(nums, target, mid + 1, h);
        }
        // Else search in the first half
        return searchTarget(nums, target, l, mid - 1);
    }
    
    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{2, 5, 6, 0, 0, 1, 2};
        int target = 0;
        
        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
        
        // Example 2
        target = 3;

        System.out.println(searchTarget(nums, target, 0, nums.length - 1));
    }
}
true
false

C++ Code

#include<bits/stdc++.h> 
using namespace std;

bool searchTarget(int *nums, int target, int l, int h) {
    // Index out of bound, element does not exist
    if (l > h)
        return false;
    // Find the middle element
    int mid = (l + h) / 2;
    // If this is the target element, return true
    if (nums[mid] == target)
        return true;
    // If nums[l] = nums[h] = nums[mid], increment l and decrement h
    if (nums[l] == nums[mid] && nums[h] == nums[mid]) {
        return searchTarget(nums, target, l + 1, h - 1);
    }
    
    // If nums[l] <= nums[mid], left half is sorted
    if (nums[l] <= nums[mid]) {
        // If the target lies in the first half, search in first half
        if (target >= nums[l] && target <= nums[mid]) {
            return searchTarget(nums, target, l, mid - 1);
        }
        // Else search in second half
        return searchTarget(nums, target, mid + 1, h);
    }

    // If first half is not sorted, then second half is sorted
    // If the target is present in the second half, search in second half
    if (target >= nums[mid] && target <= nums[h]) {
        return searchTarget(nums, target, mid + 1, h);
    }
    // Else search in the first half
    return searchTarget(nums, target, l, mid - 1);
}

int main() {
    // Example 1
    int nums[] = {2, 5, 6, 0, 0, 1, 2};
    int target = 0;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    target = 3;
    
    if (searchTarget(nums, target, 0, n - 1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

Complexity Analysis for Search an Element in Sorted Rotated Array

Time Complexity = O(log n)
Space Complexity = O(1) 
where n is the number of elements in the array.

References

Translate »