/*

     * 33.Search in sorted Array

     * 2016-4-19 by Mingyang

     * 我自己写的代码，开始没有考虑[3,1]取1得情况，所以现在需要额外的加一个部分来

     * 判断只有2个数的时候

     */

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

        int len = nums.length;

        if (len == 0 || nums == null)

            return -1;

        return searchHelper(nums, target, 0, len - 1);

    }

    public static int searchHelper(int[] nums, int target, int start, int end) {

        if (start > end)

            return -1;

        int mid = (start + end) / 2;

        //这就是多加的部分

        if(mid==start||mid==end){

            if(nums[start]==target)

                return start;

            if(nums[end]==target)

                return end;

            return -1;

        }

        if (nums[mid] == target) {

            return mid;

        } else if (nums[mid] > nums[start]) {

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

                return searchHelper(nums, target, start, mid - 1);

            } else {

                return searchHelper(nums, target, mid + 1, end);

            }

        } else {

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

                return searchHelper(nums, target, mid + 1, end);

            } else {

                return searchHelper(nums, target, start, mid - 1);

            }

        }

    }

    /*

     * 下面是网上的代码，一样的复杂度，可能更具有延展性

     * 如果target比A[mid]值要小------------------------------

     * 如果A[mid]右边有序（A[mid]<A[high]) 那么target肯定不在右边（target比右边的都得小），在左边找

     * 如果A[mid]左边有序,那么比较target和A[low]，如果target比A[low]还要小，
     *证明target不在这一区，去右边找；反之，左边找。

     * 如果target比A[mid]值要大-------------------------------

     * 如果A[mid]左边有序（A[mid]>A[low]）

     * 那么target肯定不在左边（target比左边的都得大），在右边找 如果A[mid]右边有序

     * 那么比较target和A[high]，如果target比A[high]还要大，证明target不在这一区，去左边找；反之，右边找。

     */

    public int search(int[] A, int target) {

        if (A == null || A.length == 0)

            return -1;

        int low = 0;

        int high = A.length - 1;

        while (low <= high) {    //这里是小于等于哦！！！！！！！！！！！！！----？

            int mid = (low + high) / 2;

            if (target < A[mid]) {

                if (A[mid] < A[high])// right side is sorted

                    high = mid - 1;// target must in left side

                else

                    if (target < A[low])

// target<A[mid]&&target<A[low]==>means,target cannot be in [low,mid] since this side is sorted

                    low = mid + 1;

                    else

                    high = mid - 1;

            } else if (target > A[mid]) {

                if (A[low] < A[mid])// left side is sorted

                    low = mid + 1;// target must in right side

                else

                    if (target > A[high])
// right side is sorted. If target>A[high] means target is not in this side

                    high = mid - 1;

                    else

                    low = mid + 1;

            } else

                return mid;

        }

        return -1;

    }