零 题目：算法（leetode，附思维导图 + 全副解法）300 题之（33）搜寻旋转排序数组

一 题目形容

二 解法总览（思维导图）

三 全副解法

1 计划 1

1) 代码：

// 计划 1“忽视要求，间接调用 indexOf 等函数”var search = function(nums, target) {return nums.indexOf(target);
};

2 计划 2

1) 代码：

// 计划 2“忽视要求，单指针”// 技巧：// 1）nums 是有序的，而后以某个下标进行翻转。// 2）通过观察，能够得悉 新的 nums 走势根本就是“升序 - 降序 - 升序”。// 思路（整体分 2 种状况）：// 1）状态初始化
// 2）分 2 种 状况。// 2.1）若 nums[left] <= target，则 一直判断 nums[left] === target。// 若 相等，则 间接返回 left，否则 left++。// 2.2）若 nums[right] >= target，则 一直判断 nums[right] === target。// 若 相等，则 间接返回 right，否则 right--。var search = function(nums, target) {
    // 1）状态初始化
    const l = nums.length;
    let left = 0,
        right = l - 1;
    
    // 2）分 2 种 状况。// 2.1）若 nums[left] <= target，则 一直判断 nums[left] === target。// 若 相等，则 间接返回 left，否则 left++。if (nums[left] <= target) {while(left < l) {if (nums[left] === target) {return left;}
            left++;
        }
        return -1;
    }
    // 2.2）若 nums[right] >= target，则 一直判断 nums[right] === target。// 若 相等，则 间接返回 right，否则 right--。else if(nums[right] >= target){while(right >= 0) {if (nums[right] === target) {return right;}
            right--;
        }
        return -1;
    }

    // 边界 case：[4,5,6,7,0,1,2] 3
    return -1;
}

3 计划 3

1) 代码：

// 计划 3“二分查找”。// 技巧：O(log n) 的工夫复杂度 -->“二分查找”。// 参考：// 1）https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-by-lukelee/
var search = function(nums, target) {
    const l = nums.length;
    let left = 0,
        right = l - 1;
    
    while (left < right) {let mid = parseInt((left + right) / 2);
        if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])) {left = mid + 1;}
        else {right = mid;}
    }

    return left === right && nums[left] === target ? left : -1;
};