81. 搜索旋轉(zhuǎn)排序數(shù)組 II

解題思路

二分的變形，我們之前二分查找基于這樣的一個(gè)假設(shè)：我們定位到一個(gè)元素后，這個(gè)元素的前后分別都是單調(diào)的。
但是這邊的數(shù)組是旋轉(zhuǎn)的。
所以我們需要修改的是判定邏輯

1. 如果我們可以判定出來(lái) 那邊是旋轉(zhuǎn)的，那邊是自增的。則可以通過(guò)邊界判斷
2. 如果不行，則進(jìn)行遞歸。

代碼實(shí)現(xiàn)

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