Search in Rotated Sorted Array

For sorted array, binary search works with O(logn) time complexity.

Problem:

Now, suppose an array of integers, with no duplicates, sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [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.

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

 

Solution:

Idea is, since the array is partially sorted, there are only 2 scenarios to consider.
Let mid = (start + end) / 2

Either
(1) the subarray from left to mid_th index is sorted

or
(2) the subarray from mid_th to right index is sorted


eg. arr = [4,5,6,7,0,1,2]
start = 0, end = 6, m = 3


Here, either [4,5,6,7] or [7,0,1,2] must be sorted this can be checked comparing arr[start] and arr[mid].

If arr[mid] >= subarray[start], the left subarray is sorted, else right subarray is sorted.

Now, it is easy to check if target falls within sorted range or not, and if it falls, then we we look only on sorted part of array else the remaining part.

 

Source code:

public class SearchRotatedArray {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) return mid;

            // if left part is sorted
            if (nums[start] <= nums[mid]) {
                // make sure target falls in sorted part
                if (nums[start] <= target && target < nums[mid]) { 
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {

                if (nums[mid] < target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }

    @Test
    public void test1() {
        assertEquals(0, search(new int[]{4, 5, 6, 7, 0, 1, 2}, 4));
        assertEquals(1, search(new int[]{4, 5, 6, 7, 0, 1, 2}, 5));
        assertEquals(2, search(new int[]{4, 5, 6, 7, 0, 1, 2}, 6));
        assertEquals(3, search(new int[]{4, 5, 6, 7, 0, 1, 2}, 7));
        assertEquals(4, search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
        assertEquals(5, search(new int[]{4, 5, 6, 7, 0, 1, 2}, 1));
        assertEquals(6, search(new int[]{4, 5, 6, 7, 0, 1, 2}, 2));
    }

    @Test
    public void test2() {
        assertEquals(4, search(new int[]{4, 5, 6, 7, 8, 1, 2, 3}, 8));
    }

    @Test
    public void test3() {
        assertEquals(1, search(new int[]{3, 1}, 1));
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

 

All source code is available on Github as well! Happy coding!