题目：Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

给一个排好序但是旋转过的数组，查找某个目标值的位置

例如

输入：[4,5,6,7,0,1,2]，0

输出：4

思路

类似 二分查找 的思路，每次需要判断前进的方向

code

func search(nums []int, target int) int {
lo := 0
hi := len(nums) - 1
for lo < hi {
mid := (lo + hi) / 2
if nums[mid] == target {
return mid
}
if nums[lo] <= nums[mid] {
if target >= nums[lo] && target < nums[mid] {
hi = mid - 1
} else {
lo = mid + 1
}
} else {
if target > nums[mid] && target <= nums[hi] {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
if nums[lo] == target {
return lo
} else {
return -1
}
}
 

更多内容请移步我的repo：