Leetcode33--->Search in Rotated Sorted Array(在旋转数组中找出给定的target值的位置)

题目： 给定一个旋转数组，但是你不知道旋转位置，在旋转数组中找出给定target值出现的位置；你可以假设在数组中没有重复值出现

举例：

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

在旋转后的数组中查找6，则返回index =2. 若查找10，则返回index= -1；

解题思路：

由于数组中没有重复出现的数字，因此旋转后的数组基本可以划分为两部分；因此解题思路可以转换为我们熟悉的二分查找；但是在二分查找时我们需要注意，到底在哪边查找？

1） 假设此时在[start, end]之间查找，则mid = (start + end) / 2;此时有三种情况，即nums[mid] > target, nums[mid] < target, nums[mid] = target;

2)   nums[mid] > target这种情况下，如何缩小start或者end的范围呢？

   a)     456789123, nums[mid] = 8, target =2,  此时判断条件应当是nums[start] > nums[end]（表示将原数组将数组划分为两部分，第一部分是升序，第二部分也是升序）&& nums[mid] > = nums[start](表示[start, mid]之间的数是一个严格的升序) && target < nums[start](表示所求的值在第二部分的升序中)，此时将所有的条件整合起来，则可判断要找的值一定在后半段，即start = mid + 1；否则end = mid -1

3)  nums[mid] < target的情况用同样的方法去除一半

但是要注意每次缩小的一半一定是一个升序或者降序；

代码如下：

public class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;
        while(start <= end)
        {
            mid = (start + end) / 2;
            if(target < nums[mid])
            {
                if(nums[start] > nums[end] && nums[mid] >= nums[start] && target < nums[start]) //  456789123, target =2 , 第一次舍弃掉45676
                    start = mid + 1;
                else
                    end = mid - 1;
            }
            else if(target > nums[mid])
            {
                if(nums[start] > nums[end] && nums[mid] < nums[end] && target > nums[end]) // 7812345, target= 8; 舍弃掉2345
                    end = mid - 1;
                else
                    start = mid + 1;
            }
            else // 4567123, target=7
                return mid;
        }
        
        return -1;
        
    }
}