Skip to main content

33. Search in Rotated Sorted Array

分析

从二分减治的角度分析,根据旋转点所在位置分类讨论

Pasted image 20220413222036.png

题解

func search(nums []int, target int) int {
left, right := 0, len(nums)-1

for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}

// left sorted portion
if nums[left] <= nums[mid] {
if nums[mid] > target && nums[left] <= target {
right = mid - 1
} else {
left = mid + 1
}
} else {
if nums[mid] < target && nums[right] >= target {
left = mid + 1
} else {
right = mid - 1
}
}
}

return -1
}