Simple Golang solution


  • 0
    D

    Basic idea is to check whether nums[mid] and target are in the same ascending sub-array or not, and then compare nums[mid] with target as binary search to reduce search space.

    func search(nums []int, target int) int {
        lenOfNums := len(nums)
        if lenOfNums == 0 {
            return -1
        }
        start,end,mid := 0,lenOfNums-1,0
        
        for start < end-1 {
            mid = (start+end)>>1
            if nums[mid] == target {
                return mid
            }
            if (nums[mid]<nums[start]) == (target<nums[start]) {
                if nums[mid] < target {
                    start = mid+1
                }else {
                    end = mid
                }
            }else {
                if nums[mid] < target {
                    end = mid-1
                }else {
                    start = mid
                }
            }
        }
        if nums[start] == target {
            return start
        }
        if nums[end] == target {
            return end
        }
        return -1
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.