LeetCode(78) -- 33

P33. Search in Rotated Sorted Array (Medium)

Suppose an array 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.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

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

My Solution

public class P33_SearchinRotatedSortedArray {
    public int search(int[] nums, int target) {
        int length = nums.length;
        int l = 0;
        int r = length - 1;
        int pivot = -1;
        boolean ascending = false;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mid == 0 && mid < length - 1 && nums[mid] > nums[mid + 1]) {
                pivot = mid;
                break;
            } else if (mid > 0 && nums[mid] > nums[mid - 1] && mid < length - 1 &&  nums[mid] > nums[mid + 1]) {
                pivot = mid;
                break;
            } else if (nums[mid] > nums[length - 1]) {
                l = mid + 1;
            } else if (nums[mid] < nums[length - 1]) {
                r = mid - 1;
            } else {
                pivot = length - 1;
                ascending = true;
                break;
            }
        }
        int left = bs(nums, target, 0, pivot);
        if (left != -1) {
            return left;
        }
        if (!ascending) {
            return bs(nums, target, pivot + 1, length - 1);
        }
        return -1;
    }

    private int bs(int[] nums, int target, int start, int end){
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int search = new P33_SearchinRotatedSortedArray().search(new int[]{3,1}, 1);
        System.out.println("search = " + search);
    }
}

100%

Solution

Approach 1: Binary search

class Solution {
  int [] nums;
  int target;

  public int find_rotate_index(int left, int right) {
    if (nums[left] < nums[right])
      return 0;

    while (left <= right) {
      int pivot = (left + right) / 2;
      if (nums[pivot] > nums[pivot + 1])
        return pivot + 1;
      else {
        if (nums[pivot] < nums[left])
          right = pivot - 1;
        else
          left = pivot + 1;
      }
    }
    return 0;
  }

  public int search(int left, int right) {
    /*
    Binary search
    */
    while (left <= right) {
      int pivot = (left + right) / 2;
      if (nums[pivot] == target)
        return pivot;
      else {
        if (target < nums[pivot])
          right = pivot - 1;
        else
          left = pivot + 1;
      }
    }
    return -1;
  }

  public int search(int[] nums, int target) {
    this.nums = nums;
    this.target = target;

    int n = nums.length;

    if (n == 0)
      return -1;
    if (n == 1)
      return this.nums[0] == target ? 0 : -1;

    int rotate_index = find_rotate_index(0, n - 1);

    // if target is the smallest element
    if (nums[rotate_index] == target)
      return rotate_index;
    // if array is not rotated, search in the entire array
    if (rotate_index == 0)
      return search(0, n - 1);
    if (target < nums[0])
      // search in the right side
      return search(rotate_index, n - 1);
    // search in the left side
    return search(0, rotate_index);
  }
}

Approach 2: One pass

class Solution {
  public int search(int[] nums, int target) {
    int start = 0, end = nums.length - 1;
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (nums[mid] == target) return mid;
      else if (nums[mid] >= nums[start]) {
        if (target >= nums[start] && target < nums[mid]) end = mid - 1;
        else start = mid + 1;
      }
      else {
        if (target <= nums[end] && target > nums[mid]) start = mid + 1;
        else end = mid - 1;
      }
    }
    return -1;
  }
}

这个解法最好。一遍binary search, 先检查中点值在哪一边。如果在pivot左边，说明它左边的是单增区间，再检查一下target是否落在这一区间，即可确定下一轮binary search的区间。