leetcode_33

Golang:

思路：这大概是我提交错误最多的一次。思路很简单，先二分找到变化的点，知道变化的点后，查找可以去到数组的不同区域去二分。时间复杂度是logn没有问题。思路很正确没有问题。至于为什么错这么多，状态不好，没啥耐心，强行写题，炸了。顺便一提，这道题我的代码极烂，烂到我都不想承认这是我写的！！！后面会不会改要看心情。

代码如下：

func search(nums []int, target int) int {
    if len(nums)==0 {
        return -1
    }
    if len(nums)==1{
        if target==nums[0]{
            return 0
        }else {
            return -1
        }
    }
    temp:=pointChanged(nums)
    if temp==0 {
        temp=len(nums)-1
        return binarySearch(nums,target,0,temp)
    }
    if target>=nums[0] {
        return binarySearch(nums,target,0,temp-1)
    }else{
        return binarySearch(nums,target,temp,len(nums)-1)
    }
}

func binarySearch(nums []int,target int, low int, high int) int{
    if target>nums[high]||target<nums[low]||low>high {
        return -1
    }
    middle:=(low+high)/2
    if nums[middle]>target {
        return binarySearch(nums,target,low,middle-1)
    }else if nums[middle]<target{
        return binarySearch(nums,target,middle+1,high)
    }else{
        return middle
    }
}

func pointChanged(nums []int) int {
    i,j:=0,len(nums)-1
    if nums[i]<=nums[j] {
        return 0
    }
    //考虑到时间复杂度，我们未必需要在一次遍历里找到，可以先二分找到旋转的点，再去找target
    for i<j{
        temp:=i+(j-i)/2
        //这一步是正常操作
        if nums[temp]>=nums[i]{
            i=temp
        }else{
            j=temp
        }
        if j-i==1{
            if nums[j]<nums[i]{
                return j
            }else{
                return -1
            }
        }
    }
    return j
}

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