leetcode 搜索旋转排序数组 golang

81. 搜索旋转排序数组 II

解题思路

二分的变形，我们之前二分查找基于这样的一个假设：我们定位到一个元素后，这个元素的前后分别都是单调的。
但是这边的数组是旋转的。
所以我们需要修改的是判定逻辑

1. 如果我们可以判定出来 那边是旋转的，那边是自增的。则可以通过边界判断
2. 如果不行，则进行递归。

代码实现

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
}

有疑问加站长微信联系（非本文作者）