33. Search in Rotated Sorted Array

Leetcode

https://leetcode.com/problems/search-in-rotated-sorted-array/

題目

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

解答

• 方法一

先找出整個矩陣最大值的 index (rotateIndex)，再看 target 應該是要在 rotateIndex 的左邊或右邊開始找

var search = function(nums, target) {
    const getRotateIndex = () => {
        let rotateIndex = 0;
        let low = 0;
        let high = nums.length - 1;
        
        while(low < high) {
            const mid = Math.ceil((low+high) / 2);
            if(nums[mid] > nums[rotateIndex]) {
                rotateIndex = mid;
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return rotateIndex;
    }
    
    // 找出矩陣最大值的 index
    const rotateIndex = getRotateIndex();
    // 目標值是否該從左邊開始找
    const isSearchLeftPart = target >= nums[0];
    let [low, high] = isSearchLeftPart ? [0, rotateIndex] : [rotateIndex + 1, nums.length - 1]
    // console.log(rotateIndex, low, high)
    
    while(low < high) {
        const mid = Math.floor((low+high) / 2);
        if(target === nums[mid]) return mid;
        if(target < nums[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    // 如果找到最後還是不等於 target 的話，等於不存在 return -1
    return nums[low] !== target ? -1 : low;
};

Runtime: 109 ms, faster than 14.09% of JavaScript online submissions for Search in Rotated Sorted Array.

Memory Usage: 39.6 MB, less than 83.42% of JavaScript online submissions for Search in Rotated Sorted Array.

• 方法二

每次 binary search 時都根據 mid 跟 target 及 nums[0] 之間的大小關係，決定怎麼設定下次搜尋的上下限

var search = function(nums, target) {
    let low = 0;
    let high = nums.length - 1;
    
    if(target === nums[0]) return 0;
    
    while(low < high) {
        const mid = Math.floor((low+high) / 2);
        if(target === nums[mid]) return mid;
        // 代表 mid 的位置是在 nums 矩陣的左邊
        if(nums[mid] >= nums[0]) {
            // target 在 nums 矩陣的左邊
            if(target > nums[0]) {
                if(target > nums[mid]) low = mid + 1;
                else high = mid;
            } else low = mid + 1;
        } else {
            // target 在 nums 矩陣的左邊，但是 mid 在 nums 矩陣右邊，所以 high 設成 mid
            if(target > nums[0]) high = mid;
            else {
                // target 在 nums 矩陣的右邊，mid 在 nums 矩陣右邊，且 target > nums[mid]
                // 所以往右邊找 low 設成 mid + 1
                if(target > nums[mid]) low = mid + 1;
                else high = mid;
            }
        }
    }
    return nums[low] !== target ? -1 : low;
};

Runtime: 76 ms, faster than 71.83% of JavaScript online submissions for Search in Rotated Sorted Array.

Memory Usage: 40.1 MB, less than 37.65% of JavaScript online submissions for Search in Rotated Sorted Array.

測資

let nums = [4,5,6,7,0,1,2], target = 0; // 4
// nums = [4,5,6,7,0,1,2], target = 3; // -1
// nums = [1], target = 0; // -1
// nums = [1], target = 1; // 0
// nums = [1, 3], target = 3; // 1

console.log(search(nums, target))