Search in Rotated Sorted Array

You have given a rotated array sorted in ascending order. The array is rotated at some unknown pivot point. The array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

The problem is to implement a search in O(log(N)) time that gives an idea to use a binary search.

To understand how to find element in sorted rotated array, we must understand first, what is a sorted rotated array? An array is called sorted where for all i and j such that i < j, A[i] <= A[j]. A rotation happens when last element of array is push at the start and all elements on array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again all elements are moved to right again, it’s rotation by 2 and so on.

Sorted Array

Following is the Algorithm :

  • Find a rotation index rotationIndexi.e. Actually this is the index of the smallest element in the array. Binary search works just perfect here.
  • rotationIndex splits the array into two parts. Compare nums[0] and target to identify in which part one has to look for target.
  • Perform a binary search in the chosen part of the array.
class Solution {
    int[] nums;
    int target;

    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }
        this.nums = nums;
        this.target = target;
        int len = nums.length - 1;
        int rotation = getRotationPoint();
        // When there are no rotation
        if (rotation == 0) return search(0, len);
        // Search in the left part of the array
        // First element can be the target
        if (target >= nums[0]) return search(0, rotation);
        // Search in the right part of the array
        else return search(rotation, len);
    }

    private int getRotationPoint() {
        int len = nums.length - 1;
        // when there is no rotation
        if (nums[0] < nums[len]) {
            return 0;
        }
        int left = 0, right = len;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // Next element is the rotation point
            if (nums[mid] > nums[mid + 1]) return (mid + 1);
            else if (nums[mid] > nums[left]) left = (mid + 1);
            else right = mid;
        }
        return 0;
    }

    // Binary Search for the target in the array
    private int search(int left, int right) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] > target) right = (mid - 1);
            else left = (mid + 1);
        }
        return -1;
    }
}

Complexity Analysis

  • Time complexity : O(log(N)).
  • Space complexity: O(1)

‘ ​

Categories: Binary Search

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s