原题链接
二分查找
先来看下有序数组的二分查找。
const search = function(nums, target) {
let start = 0
let end = nums.length - 1
while (start <= end) {
const mid = start + ((end - start) >> 1)
if (nums[mid] === target) return mid
if (nums[mid] < target) {
start = mid + 1
} else {
end = mid - 1
}
}
return -1
}
- 再来明确，因为本题是旋转数组，我们无法直接根据
nums[mid] 与 target 的关系来定位 target 是在 mid 的左边还是右边
- 需要分段处理，先比较
nums[mid] 与 nums[start] 的大小，来定位 mid 在左边还是右边
- 继续定位
target，判断 target 在 mid 的左边还是右边，然后分别调整边界 start 和 end
const search = function(nums, target) {
let start = 0
let end = nums.length - 1
while (start <= end) {
const mid = start + ((end - start) >> 1)
if (nums[mid] === target) return mid
if (nums[mid] >= nums[start]) {
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1
} else {
start = mid + 1
}
} else {
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1
} else {
end = mid - 1
}
}
}
return -1
}
原题链接
二分查找
先来看下有序数组的二分查找。
nums[mid]与target的关系来定位target是在mid的左边还是右边nums[mid]与nums[start]的大小，来定位mid在左边还是右边target，判断target在mid的左边还是右边，然后分别调整边界start和end