Search in Rotated Sorted Array

LeetCode Q 33 - Search in Rotated Sorted Array

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).

Solution

Code:

public int search(int[] nums, int target) {
	if (nums == null || nums.length == 0) return -1;
	// find the rotation position
	int left = 0, right = nums.length - 1;
	while (left < right) {
		int mid = (left + right) / 2;
		if (nums[mid] > nums[nums.length - 1])
			left = mid + 1;
		else
			right = mid;
	}
	// now left indicates the rotation position, i.e left is the index of minimum number in the array
	if (nums[left] == target) return left;
	if (left == 0) return binarySearch(nums, 0, nums.length - 1, target);
	if (target >= nums[0]) return binarySearch(nums, 0, left - 1, target);
	else return binarySearch(nums, left + 1, nums.length - 1, target);
}

private int binarySearch(int[] nums, int left, int right, int target) {
	while (left <= right) {
		int mid = (left + right) / 2;
		if (nums[mid] == target)
			return mid;
		else if (nums[mid] > target)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}