33. Search in Rotated Sorted Array

/**

 * 33. Search in Rotated Sorted Array

 * You are given an integer array nums sorted in ascending order (with distinct values), and an integer target.

 * Suppose that nums 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]).

 * If target is found in the array return its index, otherwise, return -1.

 * 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

*/

See the solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/search/binary_search/SearchRotated.java

There are two ways that I describe to solve the problem below.

First Approach – Find Turning Point and use it to search for the value

  • This is conceptually simple; we look for the index where rotation occurs and depending on whether the target value is greater or smaller than the starting index, we search left or right of the turning point.
  • Turning point is found via binary search
    • Check mid against start, if mid is greater than start then turning point is towards right of mid
    • Otherwise, turning point is towards left inclusive of the mid

Here is the code for first approach:

/**
 * first find the turning point and then search left or right of it
 */
public int search(int[] nums, int target) {
    if (nums.length == 0) {
        return -1;
    }
    if (nums.length == 1 && nums[0] != target) {
        return -1;
    }
    int startVal = nums[0];
    int turningPoint = findTurning(startVal, 1, nums.length - 1, nums);
    if (nums[turningPoint] == target) {
        return turningPoint;
    } else if (startVal > target) {
        return java.util.Arrays.binarySearch(nums, turningPoint, nums.length, target);
    } else {
        return java.util.Arrays.binarySearch(nums, 0, turningPoint, target);
    }
}

/**
 * start from the first index in the array compare mid-value against start value
 * if mid is greater then the turning point is to the right
 * if mid is smaller then the turning point is to the left (inclusive of the mid index)
 */
int findTurning(int startVal, int startIndex, int lastIndex, int[] nums) {
    if (startIndex >= lastIndex) {
        return lastIndex;
    }
    int mid = (startIndex + lastIndex) / 2;
    int midVal = nums[mid];
    if (midVal > startVal) {
        return findTurning(startVal, mid + 1, lastIndex, nums);
    } else {
        return findTurning(startVal, startIndex, mid, nums);
    }
}

Second approach solves in a single pass via using binary search

Steps are:

  1. Check whether rotation is towards left or right of mid
  2. Move left or right of the mid depending on how target compares against mid and start value (see inline comments in below code)

Here is the code for second approach:

int binary_search(int[] nums, int low, int high, int target) {
    while (high >= low) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if ((nums[low] > nums[mid])) {
            //rotation is on left
            if ((nums[mid] > target) || (target >= nums[low])) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else {
            //rotation is not on left
            if (target >= nums[low] && target < nums[mid]) {
                high = mid - 1; //target is between mid and low
            } else {
                low = mid + 1; //target is on right
            }
        }
    }
    return -1;
}