33. Search in Rotated Sorted Arr

循环有序数组中查找一个元素，例如 [4,5,6,7,0,1,2] 中查找0，要求复杂度 O(log(n)).

思路1：
一次二分查找，但是比有序数组的二分查找逻辑复杂一点。
// 在数组a的闭区间 [l,r] 内查找 target
func bs(a []int, target int, l, r int) int {

1. 首先查看区间是否合法, 如果 r < l, 直接返回-1
2. r == l, 区间只有一个元素，只需判断该元素是否为target
3. 取区间中间元素 m = (l+r) / 2, 判断 target落在哪个区间：
   1. target == a[m] 找到
   2. target > a[m] && target < a[l] 在右区间找 bs(a, target, m+1, r-1)
   3. target < a[m] && target > a[l] 在左区间找 bs(a, target, l+1, m-1)
   4. target > a[m] && target > a[l] 无法判定在左边还是右边区间找，需要确定 [l,m]是不是一个单调区间，如果:
      a[l] < a[m] 则是一个单调区间，则在右区间找 bs(a, target, m+1, r-1)
      否则不是一个单调区间，则在左区间找 bs(a, target, l+1, m-1)
   5. target < a[m] && target < a[l] 同理，判断是否单调区间：
      a[l] < a[m] 则是一个单调区间，则在右区间找 bs(a, target, m+1, r-1)
      否则不是一个单调区间，则在左区间找 bs(a, target, l+1, m-1)
      }

go代码如下：没有优化，可能写的比较啰嗦

func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }
    return rs(nums, target, 0, len(nums)-1)
}

func rs(a []int, target, l,r int) int {
    if r < l {
        return -1
    }
    fmt.Println(a[l:r+1])
    if target == a[l] {
        return l
    }
    if target == a[r] {
        return r
    }
    if l == r {
        return -1
    }
    m := (l + r) / 2
    if target == a[m] {
        return m
    }
    
    switch {
    case target > a[m]:
        if target < a[l] {
            return rs(a, target, m+1, r-1)
        } else {
            if a[m] < a[l] {
                return rs(a, target, l+1, m-1)
            } else {
                return rs(a, target, m+1, r-1)
            }
        }
    default: // target < a[m]
        if target > a[l] {
            return rs(a, target, l+1, m-1)
        } else {
            if a[m] < a[l] {
                return rs(a, target, l+1, m-1)
            } else {
                return rs(a, target, m+1, r-1)
            }
        }
    }
}

思路2：
两次二分查找
第一次先找拐点（数组最小值所在的点）。
第二次在正确的区间内查找，找到最小值所在的点后，两个有序区间的范围都清楚了，很容易判断target落在哪个区间内，然后在对应区间按照普通的二分查找进行查找就好了。

找最小值所在的点，递归收敛条件：a[l] < a[r] 即 [l,r]是一个有序区间。
func bs(a []int, l, r int) int {
如果 l == r 或 a[l] < a[r], [l, r] 已经是一个有序区间，返回l
如果 r - l == 1 则特殊判断一下
// a[l] > a[r]
取中点 m = (l+r)/2
如果 a[m] < a[l]，拐点应该在左区间 [l, m]；如果 a[m] >= a[l], 拐点应在右边区间 [m, r]
}

go 代码如下：

func search(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }
    if target == nums[0] {
        return 0
    }
    m := findMin(nums, 0, len(nums)-1)
    if m == 0 {
        return bs(nums, target, 0, len(nums)-1)
    }
    if target > nums[0] {
        return bs(nums, target, 0, m-1)
    } 
    return bs(nums, target, m, len(nums)-1)
}

func findMin(a []int, l, r int) int {
    if l == r || a[l] < a[r] {
        return l
    }
    if r - l == 1 {
        if a[l] > a[r] {
            return r
        } 
        return l
    }
    // a[l] > a[r]
    m := (l+r)/2
    if a[m] < a[l] {
        return findMin(a, l, m)
    } else {
        return findMin(a, m, r)
    }
}

func bs(a []int, target int, l, r int) int {
    if r < l {
        return -1
    }
    m := (l + r) / 2
    if target == a[m] {
        return m
    }
    if target > a[m] {
        return bs(a, target, m+1, r)
    }
    return bs(a, target, l, m-1)
}