leetcode33. 搜索旋转排序数组, 以下代码为什么会超时

Question

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解题思路

对数组进行二分，分成有序与无序两部分后，依情况继续二分

相关代码

var search = function(nums, target) {
    let left = 0,
        right = nums.length - 1
    while (left < right) {
        let mid = Math.ceil((left + right) / 2)
        if (nums[mid] === target) {
            return mid
        }
        // [left, mid] 为有序部分时
        if (nums[mid] > nums[left]) {
            // target 在[left, mid]的区间内
            if (nums[left] <= target && nums[mid] >= target) {
                right = mid
            } else { // target 不在区间内，向乱序部分二分
                left = mid
            }
        } else { // [mid, right] 为有序部分时
            if (nums[mid] <= target && nums[right] >= target) {
                left = mid
            } else {
                right = mid
            }
        }
    }
    return -1
};

实际看到的错误信息

当测试用例为：search([4,5,6,7,0,1,2], 3) 时，代码会超时，无法正常运行。。。
实在找不出错误，麻烦大家了

Answer 1

// Math.ceil((left + right) / 2) 改为用floor即可。。。本意是向下取整的，记错API了
Math.floor((left + right) / 2)

Answer 2

right === left + 1 时是不是可能死循环