33. Search in Rotated Sorted Array

本题来自leetcode第33题，是在看到一个高分答案后，经过自己的思考与理解后的总结，并将代码写成了较为容易理解的形式进行呈现。

本题是二分查找的一种变形题，将以往查找中的“有序数组”这一条件进行修改，变成了“给定一条旋转后的数组“。例如：[12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

当然，在解本题之前还是要先掌握二分查找，在此不进行介绍，请自行搜索。

定义：如上图所示，旋转之后的队列我们仍可以分为两部分，并标记为A与B。在上例中A就是[12, 13, 14, 15, 16, 17, 18, 19]，B就是 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]。

本题如果仍想使用二分查找，需要考虑下面两种情况：

1、mid落在A上还是落在B上？ （也就是A和B谁比较长？）

2、目标target落在A上还是落在B上。

两两结合也就有了如下四种情况：

1、mid在B，同时target在A上。 --------------->将nums[mid]看作正无穷，再进行二分查找

2、mid和target都在B上。 ---------------> 正常二分查找

3、A长B短，同时target在A上。 --------------->将nums[mid]看作负无穷，再进行二分查找

4、mid和target都在A上 --------------->正常二分查找

现在讲一下如何一个值落于A还是B上：如果一个值m >= nums[0]。则其落于A，反之，若m<nums[0],则其落于B。

 

我们现在来看看普通的二分查找：

再来看看本题：

 

最后附上源代码：

    public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left <= right)
        {
        	int mid = (left+right)/2;
        	int num = nums[mid];
        	
        	//落于左半边：>=nums[0] ,落于右半边：<nums[0]
        	//mid在右边，而target在左边
        	if(nums[mid] < nums[0] && target >= nums[0])
        	{
        		num = Integer.MAX_VALUE;
        	}
        	//mid在左边，而target在右边
        	else if(nums[mid] >= nums[0] && target < nums[0])
        	{	
        		num = Integer.MIN_VALUE;
        	}
        	
        	if(num < target)
        	{
        		left = mid+1;
        	}
        	else if(num > target)
        	{
        		right = mid-1;
        	}
        	else return mid;
        }
        return -1;
    }