LintCode 62 · Search in Rotated Sorted Array.java

	public class Solution {
	/**
	* @param A: an integer rotated sorted array
	* @param target: an integer to be searched
	* @return: an integer
	*/
	public int search(int[] nums, int target) {
	// Binary Search, regardless of smoke screen, Time: O(n logn), just draw a picture, be patient and turn on your analytical mode.
	// handle corner cases.
	if (nums == null || nums.length == 0) {
	return -1;
	}
	int n = nums.length;
	int begin = 0, end = n - 1;
	while (begin + 1 < end) {
	// avoid integer overflow
	int mid = (end - begin) / 2 + begin;
	// found the answer
	if (nums[mid] == target) {
	return mid;
	}
	// avoid duplications
	if (nums[mid] == nums[begin]) {
	begin++;
	continue;
	}
	// Case-by-case discussion
	if (nums[mid] > nums[begin]) {
	if (target >= nums[begin] && target <= nums[mid]) {
	end = mid;
	} else {
	begin = mid;
	}
	} else {
	if (target >= nums[mid] && target <= nums[end]) {
	begin = mid;
	} else {
	end = mid;
	}
	}
	}
	// handle the rest.
	if (nums[begin] == target) {
	return begin;
	}
	if (nums[end] == target) {
	return end;
	}
	return -1;
	}
	}

view raw LintCode 62 · Search in Rotated Sorted Array.java hosted with ❤ by GitHub