-
Notifications
You must be signed in to change notification settings - Fork 24
Open
Labels
@Geekhyt
Description
二分查找
先来看下有序数组的二分查找。
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 }
- 时间复杂度:O(logn)
- 空间复杂度:O(1)