Search in Rotated Sorted Array

Problem Statement

Given an array of distinct elements, which is formed from some places rotation of a sorted array, find if a given element is present in the array or not.

Sample Test Cases :

Input 1:

a[] = [4, 5, 6, 7, 8, 9, 1, 2, 3]

sum = 6

Output 1:

2

Explanation 1:

The value of 2 is found in the array a[] at index 2.

Input 2:

a[] = [4, 5, 6, 7, 8, 9, 1, 2, 3]

sum = 12

Output 2:

-1

Explanation 2:

Since the value of 12 is not present in the given array, we return -1.

Naive Approach

The naive approach to solve this problem is to linearly iterate on the array, and check if the current element is equal to the target element or not.

Code / Implementation:

C++ Code

int findInArray(vector < int > & a, int target) {
  return find(a.begin(), a.end(), target) == a.end() ? -1 : find(a.begin(), a.end(), target) - a.begin();
}

Java Code

public static int findInArray(int[] a, int target) {
  int found = -1;
  for (int i = 0; i < a.length; i++) {
    if (a[i] == target) {
      found = i;
      break;
    }
  }
  return found;
}

Python Code

def findInArray(a, target):
    for i in range(len(a)):
        if a[i] == target:
            return i
    return -1

Complexity Analysis:

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

Optimal Approach(With Binary Search)

We can solve this problem optimally with a single recursive Binary Search. The algorithm is implemented as follows:

• Initialize the recursive function with 2 pointers, left = 0, and right = n – 1.
• Find the mid of the range mid = (left + right) / 2.
• If the range [left, mid] is sorted,
  • If the target lies in that range, recursively go to the range [left, mid].
  • Else go to the range [mid + 1, right].
• Else, we go to the range [mid + 1, right] (since it must be sorted),
  • If the target lies in the range, recursively go to the range [mid + 1, right].
  • Else go to the range [left, mid]. 

Implementation:

C++ Code

int findInArray(vector < int > & a, int left, int right, int target) {
  if (left > right) {
    return -1;
  }
  int mid = (left + right) / 2;
  if (a[mid] == target) {
    return mid;
  }
  if (a[mid] >= a[left]) {
    if (target >= a[left] && target <= a[mid]) {
      return findInArray(a, left, mid - 1, target);
    } else {
      return findInArray(a, mid + 1, right, target);
    }
  } else {
    if (target >= a[mid] && target <= a[right]) {
      return findInArray(a, mid + 1, right, target);
    } else {
      return findInArray(a, left, mid - 1, target);
    }
  }
}

Java Code

public static int findInArray(int[] a, int left, int right, int target) {
  if (left > right) {
    return -1;
  }
  int mid = (left + right) / 2;
  if (a[mid] == target) {
    return mid;
  }
  if (a[mid] >= a[left]) {
    if (target >= a[left] && target <= a[mid]) {
      return findInArray(a, left, mid - 1, target);
    } else {
      return findInArray(a, mid + 1, right, target);
    }
  } else {
    if (target >= a[mid] && target <= a[right]) {
      return findInArray(a, mid + 1, right, target);
    } else {
      return findInArray(a, left, mid - 1, target);
    }
  }
}

Python Code

def findInArray(a, left, right, target):
    if left > right:
        return -1
    mid = (left + right) // 2
    if a[mid] == target:
        return mid
    if a[mid] >= a[left]:
        if target >= a[left] and target <= a[mid]:
            return findInArray(a, left, mid - 1, target)
        else:
            return findInArray(a, mid + 1, right, target)
    else:
        if target >= a[mid] and target <= a[right]:
            return findInArray(a, mid + 1, right, target)
        else:
            return findInArray(a, left, mid - 1, target)

Complexity Analysis:

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

Practice Problem:

• Rotated Sorted Array Search

FAQs

Q.1: Will the binary search approach work if the array has duplicate elements?

Ans:  The approach will not work if the array has duplicate elements because we won’t be able to decide whether to recurse for the left or right half, in case of duplicates occurring.

Q.2: What are the base cases for this recursive approach?

Ans: If the left pointer, exceeds the right pointer, the function returns -1. Also if the current element, equals the target element, we return the index of this element. These are the base cases of the recursion.