33. 搜索旋转排序数组

题意：

解题思路：

思路：
1 2 3 4 5 6 7 可以大致分为两类，
第一类 2 3 4 5 6 7 1 这种，也就是 nums[low] <= nums[mid]。此例子中就是 2 <= 5。
这种情况下，前半部分有序。因此如果 nums[low] <= target < nums[mid]，则在前半部分找，否则去后半部分找。
第二类 6 7 1 2 3 4 5 这种，也就是 nums[low] > nums[mid]。此例子中就是 6 > 2。
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[high]，则在后半部分找，否则去前半部分找。

PHP代码实现：

class Solution {
    function search($nums, $target) {
        if (count($nums) == 0) return -1;
        $low = 0;
        $high = count($nums) - 1;
        while ($low <= $high) {
            $mid = $low + floor(($high - $low) >> 1);
            if ($nums[$mid] == $target) return $mid;
            //前半部分有序,注意此处用小于等于
            if ($nums[$mid] >= $nums[$low]) {
                    //target在前半部分
                if ($target >= $nums[$low] && $target < $nums[$mid]) {
                    $high = $mid - 1;
                } else $low = $mid + 1;
            } else {
                if ($target > $nums[$mid] && $target <= $nums[$high]) {
                    $low = $mid + 1;
                } else $high = $mid - 1;
            }
        }
        return -1;
    }
}

GO代码实现：

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