循環(huán)有序數(shù)組中查找一個(gè)元素，例如 [4,5,6,7,0,1,2] 中查找0，要求復(fù)雜度 O(log(n)).

思路1：
一次二分查找，但是比有序數(shù)組的二分查找邏輯復(fù)雜一點(diǎn)。
// 在數(shù)組a的閉區(qū)間 [l,r] 內(nèi)查找 target
func bs(a []int, target int, l, r int) int {

1. 首先查看區(qū)間是否合法, 如果 r < l, 直接返回-1
2. r == l, 區(qū)間只有一個(gè)元素，只需判斷該元素是否為target
3. 取區(qū)間中間元素 m = (l+r) / 2, 判斷 target落在哪個(gè)區(qū)間：
   1. target == a[m] 找到
   2. target > a[m] && target < a[l] 在右區(qū)間找 bs(a, target, m+1, r-1)
   3. target < a[m] && target > a[l] 在左區(qū)間找 bs(a, target, l+1, m-1)
   4. target > a[m] && target > a[l] 無(wú)法判定在左邊還是右邊區(qū)間找，需要確定 [l,m]是不是一個(gè)單調(diào)區(qū)間，如果:
      a[l] < a[m] 則是一個(gè)單調(diào)區(qū)間，則在右區(qū)間找 bs(a, target, m+1, r-1)
      否則不是一個(gè)單調(diào)區(qū)間，則在左區(qū)間找 bs(a, target, l+1, m-1)
   5. target < a[m] && target < a[l] 同理，判斷是否單調(diào)區(qū)間：
      a[l] < a[m] 則是一個(gè)單調(diào)區(qū)間，則在右區(qū)間找 bs(a, target, m+1, r-1)
      否則不是一個(gè)單調(diào)區(qū)間，則在左區(qū)間找 bs(a, target, l+1, m-1)
      }

go代碼如下：沒(méi)有優(yōu)化，可能寫(xiě)的比較啰嗦

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：
兩次二分查找
第一次先找拐點(diǎn)（數(shù)組最小值所在的點(diǎn)）。
第二次在正確的區(qū)間內(nèi)查找，找到最小值所在的點(diǎn)后，兩個(gè)有序區(qū)間的范圍都清楚了，很容易判斷target落在哪個(gè)區(qū)間內(nèi)，然后在對(duì)應(yīng)區(qū)間按照普通的二分查找進(jìn)行查找就好了。

找最小值所在的點(diǎn)，遞歸收斂條件：a[l] < a[r] 即 [l,r]是一個(gè)有序區(qū)間。
func bs(a []int, l, r int) int {
如果 l == r 或 a[l] < a[r], [l, r] 已經(jīng)是一個(gè)有序區(qū)間，返回l
如果 r - l == 1 則特殊判斷一下
// a[l] > a[r]
取中點(diǎn) m = (l+r)/2
如果 a[m] < a[l]，拐點(diǎn)應(yīng)該在左區(qū)間 [l, m]；如果 a[m] >= a[l], 拐點(diǎn)應(yīng)在右邊區(qū)間 [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)
}