Arrays: Program to search an element in a sorted and rotated array

We have an integer array nums which is sorted in ascending order (with distinct values).

nums is possibly rotated at an unknown pivot index k(1<= k < nums.length) such that the resulting array is [nums[k], nums[k+1], … , nums[n-1], nums[0], nums[1], … , nums[k-1]] (0 indexed). 

For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Approach

This can be solved using Binary Search.

Binary Search is a searching algorithm used in a sorted array. It searches for the given element by repeatedly dividing the search interval in half. 

In binary search it is crucial to have a sorted array as an input. It ensures that each index divides the array into two sorted halves.

However, in this case the array is sorted and rotated, which no longer ensures the above property of sorted array.

Though the array is rotated, we can clearly notice that for every index, one of the 2 halves will always be sorted.

Hence, the solution will be a two step process:

• First, identify the sorted half of the array. 
• Once found, determine if the target is located within this sorted half. 
  • If not, eliminate that half from further consideration. 
  • Conversely, if the target does exist in the sorted half, eliminate the other half.

1. Place the 2 pointers i.e. low and high: 
   1. low: will point to the first index,
   2. high: will point to the last index.
2. While low < high:
   1. Calculate the ‘mid’, mid = (low+high) // 2 ( ‘//’ refers to integer division)
   2. Check if arr[mid] == target: If it is, return the index mid.
   3. Identify the sorted half, check where the target is located, and then eliminate one half accordingly:
      1. If arr[low] <= arr[mid]: This condition ensures that the left part is sorted.
         1. If arr[low] <= target && target <= arr[mid]: It signifies that the target is in this sorted half. So, we will eliminate the right half (high = mid-1).
         2. Otherwise, the target does not exist in the sorted half. So, we will eliminate this left half by doing low = mid+1.
      2. Otherwise, if the right half is sorted:
         1. If arr[mid] <= target && target <= arr[high]: It signifies that the target is in this sorted right half. So, we will eliminate the left half (low = mid+1).
         2. Otherwise, the target does not exist in this sorted half. So, we will eliminate this right half by doing high = mid-1.
   4. Once, the ‘mid’ points to the target, the index will be returned.
3. If no index is found, we will return -1.

Complexity

Time Complexity: O(logn) where n is the size of the given array. Here we use a binary search algorithm which leads us to logn time complexity.

Space Complexity : O(1) because we don’t create any auxiliary space here.

Java Code

import java.util.*;

public class SearchElementInSortedAndRotatedArray{
    
    static int search(int array[], int target) {
        int first = 0; 
        int last = array.length - 1;

        while (first <= last) {
            int mid = (first + last) >> 1;
            if (array[mid] == target)
                return mid;

            if (array[first] <= array[mid]) {
                if (array[first] <= target && array[mid] >= target)
                    last = first - 1; 
                else
                    first = mid + 1;
            } else {
                if (array[mid] <= target && target <= array[last])
                    first = mid + 1;
                else
                    last = mid - 1;
            }
        }
        return -1; 
    }
    
    public static void main(String args[]) {
        int array[] = {4,5,6,1,2,3};
        int target = 3;
        System.out.println("The index in which the number is present is " + search(array, target));
    }
}

Output 

The index in which the number is present is 5.