/**

 * Created by lvhao on 2017/6/30.

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

 思路是目标值肯定在一个升序子序列中（可能子序列很短，但是肯定存在），目标就是找到这个子序列然后用二分法找到值

 找目标序列的时候也是用二分法，判断的依据是mid值比fin值大的话说明左边是升序，小的话，右边是升序，然后在利用升序序列的的

 首尾值判断目标值是否在里边，在里边就用二分法找值，不在里边就改变fin或者sta值，继续循环找，注意二分法的时候while的判断

 条件是sta<= fin,如果没有=的话，两个数的情况判断不出来。

 */

public class Q33SearchRotatedArray {

    public static void main(String[] args) {

        int[] nums = new int[]{3,1};

        int target = 1;

        int res = search(nums,target);

        System.out.println(res);

    }

    public static  int search(int[] nums, int target) {

        int len = nums.length;

        //判断特殊情况

        if(len == 1 && nums[0] == target)

        {

            return 0;

        }

        int sta = 0,fin = len-1,mid,index = -1;

        //注意等号

        while(sta <= fin)

        {

            mid = (sta + fin)/2;

            if(nums[mid] < nums[fin])

            {

                if(target <= nums[fin] && target >= nums[mid])

                {

                    index = binarySearch(nums,mid,fin,target);

                    //找到值之后立即break

                    break;

                }

                else

                    fin = mid -1;

            }

            else

            {

                if(target <= nums[mid] && target >= nums[sta])

                {

                    index = binarySearch(nums,sta,mid,target);

                    break;

                }

                else

                    sta = mid + 1;

            }

        }

        return index;

    }

    public static int binarySearch(int[] nums,int sta,int fin,int target)

    {

        int mid,index = -1;

        //注意等号

        while (sta <= fin)

        {

            mid = (sta + fin)/2;

            if(target == nums[mid])

            {

                index = mid;

                break;

            }

            else if (target < nums[mid])

                fin = mid-1;

            else

                sta = mid+1;

        }

        return index;

    }

}