81. 搜索旋转排序数组 II

题意：

解题思路：

思路：二分法，分三种情况考虑：
1. 10111 和 1110111101 这种。此种情况下 nums[low] == nums[mid]，
        分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
2. 2 3 4 5 6 7 1 这种，也就是 nums[low] < nums[mid]。此例子中就是 2 < 5；
        这种情况下，前半部分有序。因此如果 nums[low] <= target <= nums[mid]，则在前半部分找，否则去后半部分找。
3. 6 7 1 2 3 4 5 这种，也就是 nums[high] > nums[mid]。此例子中就是 5 > 2；
        这种情况下，后半部分有序。因此如果 nums[mid] < target <= nums[high]。则在后半部分找，否则去前半部分找

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Boolean
     */
    function search($nums, $target) {
        $low = 0;
        $high = count($nums) - 1;
        while ($low < $high) {
            $mid = $low + floor(($high - $low) / 2);
            if ($nums[$mid] == $target) {
                return true;
            }
            if ($nums[$low] < $nums[$mid]) {//左半有序
                if ($nums[$mid] >= $target && $nums[$low] <= $target) {
                    $high = $mid - 1;
                } else {
                    $low = $mid + 1;
                }
            } else if ($nums[$high] > $nums[$mid]) {//右边部分有序
                if ($nums[$mid] <= $target && $nums[$high] >= $target) {
                    $low = $mid + 1;
                } else {
                    $high = $mid - 1;
                }
            } else {
                //去重
                if ($nums[$mid] == $nums[$low]) {
                    $low++;
                } else {
                    $high--;
                }
            }
        }
        return $nums[$low] == $target;
    }
}

GO代码实现：

func search(nums []int, target int) bool {
    low := 0
    high := len(nums) - 1
    for low <= high {
        mid := low + (high-low)>>1
        if nums[mid] == target {
            return true
        }
        if nums[low] < nums[mid] {
            if target <= nums[mid] && target >= nums[low] {
                high = mid - 1
            } else {
                low = mid + 1
            }
        } else if (nums[high] > nums[mid]) {
            if target >= nums[mid] && target <= nums[high] {
                low = mid + 1
            } else {
                high = mid - 1
            } 
        } else {
            if nums[mid] == nums[low] {
                low++
            } else {
                high--
            }
        }
    }
    return false
}