81. Search in Rotated Sorted Arr

题目

有一个非降序排列的数组 nums，这个数组在某一个位置发生了旋转，给定一个目标数 target。判断这个目标数是否在数组中。

解析

首先看一下旋转数组的性质。
当一个数组发生旋转的时候，其末尾值是小于等于起始值的。
而如果一个数组没有发生旋转的时候，其末尾值是大于等于起始值的。
所以有三种情况，

1. 末尾大于起始，未发生旋转，二分法查找
2. 末尾小于起始，发生旋转，旋转二分查找
3. 末尾等于起始，如果未旋转，则全部相等，如果旋转，按 2 处理

关于旋转二分查找是否具有普遍求解。对于一个已经证明是旋转数组的数字。

1. 对于一个旋转数组，如果其前后两个元素相等，说明一定发生了旋转，我们消去这两个元素，其剩下的可能是旋转的，也可能是非旋转的
2. 对于非旋转的，我们走一般二分求解即可
3. 对于旋转的，取一个中间值
4. 我们一定能得到一个非降序区间，和一个旋转区间
5. 判断结果可能在旋转区间，或是非降序区间。

伪代码

if nums[i] == nums[j]
  return func(nums[i+1:j-1])
if if nums[j] > nums[i]
  return commid(nums[i,j])
mid = i+j/2
if nums[mid] >= nums[i]
  return commid(nums[i,mid]) || rotmid(nums[mid,j])
if nums[mid] <= nums[j]
  return rotmid(nums[i,mid]) || rotmid(nums[mid, j])  

代码

func search(nums []int, target int) bool {
    i:=0
    j:=len(nums)-1
    for i<j {
        if nums[i] == target || nums[j] == target {
            return true
        }
        if nums[i] == nums[j] {
            i++
            j--
            continue
        }
        if nums[i] < nums[j] {
            return searchmid(nums, target, i, j)
        }
        return searchrot(nums, target, i,j)
    }
    return nums[i]==target
}

func searchrot(nums []int, target,i,j int) bool {
    if target > nums[j] && target < nums[i] {
        return false
    }
    if j-i<=1 {
        return false
    }
    mid := (i+j)/2
    if nums[mid] == target {
        return true
    }
    if nums[i] <= nums[mid] {
        return searchmid(nums, target, i, mid) || searchrot(nums, target, mid, j)
    }
    if nums[j] >= nums[mid] {
        return searchrot(nums, target, i, mid) || searchmid(nums, target, mid, j)
    }
    return false
}

func searchmid(nums []int, target, i,j int) bool {
    if target > nums[j] || target < nums[i] {
        return false
    }
    for i<j {
        mid := (i+j)/2
        if nums[mid] == target {
            return true
        }
        if nums[mid] < target {
            i = mid+1
        }
        if nums[mid] > target {
            j = mid-1
        }
    }
    return nums[i] == target
}