Solution: Search in Rotated Sorted Array

Let's solve the Search in Rotated Sorted Array problem using the Modified Binary Search pattern.

We'll cover the following

Statement

Given a sorted integer array, nums, and an integer value, target, the array is rotated by some arbitrary number. Search and return the index of target in this array. If the target does not exist, return -11.

An original sorted array before rotation is given below:

g array 1 10 20 47 59 63 75 88 99 107 120 133 155 162 176 188 199 200 210 222

After rotating this array 6 times, it changes to:

g array 176 188 199 200 210 222 1 10 20 47 59 63 75 88 99 107 120 133 155 162

Constraints:

  • All values in nums are unique.
  • The values in nums are sorted in ascending order.
  • The array may have been rotated by some arbitrary number.
  • 1≤1 \leq nums.length ≤1000\leq 1000
  • −104≤-10^4 \leq nums[i] ≤104\leq 10^4
  • −104≤-10^4 \leq target ≤104\leq 10^4

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach is to traverse the whole array while searching for our target.

We get the required solution, but at what cost? The time complexity is O(n)O(n) because we traverse the array only once, and the space complexity is O(1)O(1). Let’s see if we can use the modified binary search pattern to design a more efficient solution.

Optimized approach using modified binary search

We’ve been provided with a rotated array to apply binary search, which is faster than the above linear approach. We can change the part we have to search based on our three pointers—low, mid, and high.

The slides below illustrate how we would like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

Let’s start with learning how to use binary search to find a target value in an unrotated sorted array. We can do this either iteratively or recursively. Let’s look at the iterative version first.

import java.util.*;
class Solution {
    public static int binarySearch(List<Integer> nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        int mid = 0;
        while (start <= end) {
            // Finding the mid using integer division
            mid = start + (end - start) / 2;
            // Target value is present at the middle of the array
            if (nums.get(mid) == target)
                return mid;
            // If the target value is greater than the middle, ignore the first half
            else if (nums.get(mid) < target)
                start = mid + 1;
            // If the target value is less than the middle, ignore the second half
            else
                end = mid - 1;
        }
        return -1;
    }
    // Driver code
    public static void main(String args[]) {
        List<List<Integer>> numList = Arrays.asList(
            Arrays.asList(1, 2, 3, 4, 5, 6, 7),
            Arrays.asList(10, 20, 30, 40, 50, 60),
            Arrays.asList(12, 24, 35, 47, 58, 69, 72, 83, 94),
            Arrays.asList(5, 13, 28, 41, 56, 63, 77, 82, 99, 105),
            Arrays.asList(5, 7, 12, 17, 21, 28, 33, 37, 41, 48, 52, 57, 62, 68, 72)
        );
        List<Integer> targetList = Arrays.asList(1, 50, 12, 56, 5);
        for (int i = 0; i < targetList.size(); i++) {
            System.out.println((i + 1) + ".\tSorted array: " + numList.get(i) +
                "\n\ttarget " + targetList.get(i) +
                " found at index " + binarySearch(numList.get(i), targetList.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Search in Sorted Array

Next, let’s look at the recursive version.

import java.util.*;
class Solution {
    public static int binarySearch(List<Integer> nums, int start, int end, int target) {
        if (start > end)
            return -1;
        // Finding the mid using integer division
        int mid = start + (end - start) / 2;
        // Target value is present at the middle of the array
        if (nums.get(mid) == target)
            return mid;
        // If the target value is greater than the middle, ignore the first half
        else if (nums.get(mid) < target)
            return binarySearch(nums, mid + 1, end, target);
        // If the target value is less than the middle, ignore the second half
        return binarySearch(nums, start, mid - 1, target);
    }
    // Driver code
    public static void main(String args[]) {
        List<List<Integer>> numList = Arrays.asList(
            Arrays.asList(1, 2, 3, 4, 5, 6, 7),
            Arrays.asList(10, 20, 30, 40, 50, 60),
            Arrays.asList(12, 24, 35, 47, 58, 69, 72, 83, 94),
            Arrays.asList(5, 13, 28, 41, 56, 63, 77, 82, 99, 105),
            Arrays.asList(5, 7, 12, 17, 21, 28, 33, 37, 41, 48, 52, 57, 62, 68, 72)
        );
        List<Integer> targetList = Arrays.asList(1, 50, 12, 56, 5);
        for (int i = 0; i < targetList.size(); i++) {
            System.out.println((i + 1) + ".\tSorted array: " + numList.get(i) +
                "\n\ttarget " + targetList.get(i) +
                " found at index " + binarySearch(numList.get(i), 0, numList.get(i).size() - 1, targetList.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Search in Sorted Array

Binary search works with arrays that are completely sorted. However, the nums array that we’re provided may not have this property if it’s rotated. Therefore, we have to modify our binary search to accommodate this rotation.

You may notice that at least one half of the array is always sorted—if the array is rotated by less than half the length of the array, at least the second half of the array will still be sorted. Contrarily, if the array is rotated by more than half the length of the array, then at least the first half of the array will be sorted. We can use this property to our advantage and modify the binarySearch function as follows:

  • If the target value lies within the sorted half of the array, our problem is a basic binary search.

  • Otherwise, discard the sorted half and keep examining the unsorted half.

Here is how we go about implementing the iterative approach for this:

import java.util.*;
class Solution {
    public static int binarySearchRotated(List<Integer> nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        while (start <= end) {
            // Finding the mid using integer division
            int mid = start + (end - start) / 2;
            // Target value is present at the middle of the array
            if (nums.get(mid) == target)
                return mid;
            // start to mid is sorted
            if (nums.get(start) <= nums.get(mid)) {
                if (nums.get(start) <= target && target < nums.get(mid)) {
                    end = mid - 1; // target is within the sorted first half of the array
                } else {
                    start = mid + 1; // target is not within the sorted first half, so let’s examine the unsorted second half
                }
            }
            // mid to end is sorted
            else {
                if (nums.get(mid) < target && target <= nums.get(end))
                    start = mid + 1; // target is within the sorted second half of the array
                else
                    end = mid - 1; // target is not within the sorted second half, so let’s examine the unsorted first half
            }
        }
        return -1;
    }
    // Driver code
    public static void main(String args[]) {
        List<List<Integer>> numList = Arrays.asList(
            Arrays.asList(5, 6, 7, 1, 2, 3, 4),
            Arrays.asList(40, 50, 60, 10, 20, 30),
            Arrays.asList(47, 58, 69, 72, 83, 94, 12, 24, 35),
            Arrays.asList(77, 82, 99, 105, 5, 13, 28, 41, 56, 63),
            Arrays.asList(48, 52, 57, 62, 68, 72, 5, 7, 12, 17, 21, 28, 33, 37, 41)
        );
        List<Integer> targetList = Arrays.asList(1, 50, 12, 56, 5);
        for (int i = 0; i < targetList.size(); i++) {
            System.out.println((i + 1) + ".\tSorted array: " + numList.get(i) +
                "\n\ttarget " + targetList.get(i) +
                " found at index " + binarySearchRotated(numList.get(i), targetList.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Search in Rotated Sorted Array

The recursive approach is shown below:

import java.util.*;
class Solution {
    public static int binarySearch(List<Integer> nums, int start, int end, int target) {
        if (start > end)
            return -1;
        // Finding the mid using integer division
        int mid = start + (end - start) / 2;
        // Target value is present at the middle of the array
        if (nums.get(mid) == target)
            return mid;
        // start to mid is sorted
        if (nums.get(start) <= nums.get(mid)) {
            if (nums.get(start) <= target && target < nums.get(mid)) {
                // target is within the sorted first half of the array
                return binarySearch(nums, start, mid - 1, target);
            }
            // target is not within the sorted first half, so let’s examine the unsorted second half
            return binarySearch(nums, mid + 1, end, target);
        }
        // mid to end is sorted
        else {
            if (nums.get(mid) < target && target <= nums.get(end))
                return binarySearch(nums, mid + 1, end, target); // target is within the sorted second half of the array
            return binarySearch(nums, start, mid - 1, target); // target is not within the sorted second half, so let’s examine the unsorted first half
        }
    }
    public static int binarySearchRotated(List<Integer> nums, int target) {
        return binarySearch(nums, 0, nums.size() - 1, target);
    }
    // Driver code
    public static void main(String args[]) {
        List<List<Integer>> numList = Arrays.asList(
            Arrays.asList(5, 6, 7, 1, 2, 3, 4),
            Arrays.asList(40, 50, 60, 10, 20, 30),
            Arrays.asList(47, 58, 69, 72, 83, 94, 12, 24, 35),
            Arrays.asList(77, 82, 99, 105, 5, 13, 28, 41, 56, 63),
            Arrays.asList(48, 52, 57, 62, 68, 72, 5, 7, 12, 17, 21, 28, 33, 37, 41)
        );
        List<Integer> targetList = Arrays.asList(1, 50, 12, 56, 5);
        
        for (int i = 0; i < targetList.size(); i++) {
            System.out.println((i + 1) + ".\tSorted array: " + numList.get(i) +
                "\n\ttarget " + targetList.get(i) +
                " found at index " + binarySearchRotated(numList.get(i), targetList.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Search in Rotated Sorted Array

Just the code

Here’s the complete solution to this problem:

The iterative approach:

import java.util.*;
class Solution {
    public static int binarySearchRotated(List<Integer> nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums.get(mid) == target)
                return mid;
            if (nums.get(start) <= nums.get(mid)) {
                if (nums.get(start) <= target && target < nums.get(mid)) {
                    end = mid - 1;
                } else
                    start = mid + 1;
            } else {
                if (nums.get(mid) < target && target <= nums.get(end))
                    start = mid + 1;
                else
                    end = mid - 1;
            }
        }
        return -1;
    }
    // Driver code
    public static void main(String args[]) {
        List<List<Integer>> numList = Arrays.asList(
            Arrays.asList(5, 6, 7, 1, 2, 3, 4),
            Arrays.asList(40, 50, 60, 10, 20, 30),
            Arrays.asList(47, 58, 69, 72, 83, 94, 12, 24, 35),
            Arrays.asList(77, 82, 99, 105, 5, 13, 28, 41, 56, 63),
            Arrays.asList(48, 52, 57, 62, 68, 72, 5, 7, 12, 17, 21, 28, 33, 37, 41)
        );
        List<Integer> targetList = Arrays.asList(1, 50, 12, 56, 5);
        
        for (int i = 0; i < targetList.size(); i++) {
            System.out.println((i + 1) + ".\tSorted array: " + numList.get(i) +
                "\n\ttarget " + targetList.get(i) +
                " found at index " + binarySearchRotated(numList.get(i), targetList.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Search in Rotated Sorted Array

The recursive approach:

import java.util.*;
class Solution {
    public static int binarySearch(List<Integer> nums, int start, int end, int target) {
        if (start > end) return -1;
        int mid = start + (end - start) / 2;
        if (nums.get(mid) == target) return mid;
        if (nums.get(start) <= nums.get(mid)) {
            if (nums.get(start) <= target && target < nums.get(mid)) {
                return binarySearch(nums, start, mid - 1, target);
            }
            return binarySearch(nums, mid + 1, end, target);
        } else {
            if (nums.get(mid) < target && target <= nums.get(end)) {
                return binarySearch(nums, mid + 1, end, target);
            }
            return binarySearch(nums, start, mid - 1, target);
        }
    }
    public static int binarySearchRotated(List<Integer> nums, int target) {
        return binarySearch(nums, 0, nums.size() - 1, target);
    }
    // Driver code
    public static void main(String args[]) {
        List<List<Integer>> numList = Arrays.asList(
            Arrays.asList(5, 6, 7, 1, 2, 3, 4),
            Arrays.asList(40, 50, 60, 10, 20, 30),
            Arrays.asList(47, 58, 69, 72, 83, 94, 12, 24, 35),
            Arrays.asList(77, 82, 99, 105, 5, 13, 28, 41, 56, 63),
            Arrays.asList(48, 52, 57, 62, 68, 72, 5, 7, 12, 17, 21, 28, 33, 37, 41)
        );
        List<Integer> targetList = Arrays.asList(1, 50, 12, 56, 5);
        for (int i = 0; i < targetList.size(); i++) {
            System.out.println((i + 1) + ".\tSorted array: " + numList.get(i) +
                    "\n\ttarget " + targetList.get(i) + " found at index " +
                    binarySearchRotated(numList.get(i), targetList.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Search in Rotated Sorted Array

Solution summary

To recap, the solution to this problem can be divided into the following five parts:

  1. Divide the array into two halves.

  2. Check if the first half is sorted, and if it is, do the following.

    • Check if the target lies in this range, and if it does, perform a binary search on this half for the target value.

    • If the target does not lie in this range, move to the second half of the array.

  3. If the first half is not sorted, check if the target lies in the second half.

    • If the target lies in this half, perform a binary search on this half for the target value.

    • If the target does not lie in the second half, examine the first half.

  4. If the target value is not found at the end of this process, we return -11.

Time complexity

The time complexity of both approaches is O(log⁡n)O(\log n) since we divide the array into two halves at each step.

Space complexity

The space complexity of the iterative solution is O(1)O(1) since no new data structure is being created.

The space complexity of the recursive solution is O(log⁡n)O(\log n), where nn is the number of elements present in the array and log⁡n\log n is the maximum number of recursive calls needed to find the target.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.