二十分钟入门二分查找

今天介绍下二分查找这个算法套路，学会此招，你的内力会精进三分，与路边程序员能立马拉开差距！

题目描述

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

**进阶：**你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

题解

这题看着简单，因为常规解法很容易想到，直接暴力遍历就可以了。看代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    var res = -1
    for(var i = 0; i <nums.length; i++) {
        if(nums[i] === target) {
            res = i
            return res;
        }
    }
    return res;
};

这种解法的时间复杂度是O(n);

此题还有更好的解法：二分查找！它的时间复杂度是O(logn)，题目中也提到了这个，向我们发起了挑战！来看如何接招吧！

先介绍下二分查找这个算法，非常适合这种题目。这是有一定套路的解法，主要就是约定几个索引位，从数组两头向中间进行夹逼推进，最终找到目标值。而在每次推进过程中都会舍弃掉当前资源中的一半，这样算下去，最终的时间复杂度就是O(logn)。它的套路解法还有一个代码模板，适合初学的人理解记忆：

left,right = 0,len(array) -1
while left<= right;
 mid = (left + right)/2
 if array[mid] == target;
  #find the target!!
        break or return result
 elif array[mid]< target:
     left = mid + 1
 else:
     right = mid - 1

简单解释就是，初始变量设置数组的一头一尾的索引位置，然后取其中间位置，这个中间位置就可以将数组分为两段，接着去判断目标值所在的大概位置，同时调整查找范围，这样不断的排除查找，最终锁定目标值。

落到此题目中来，原本的一个顺序数组在某个位置旋转了，这样一来，取了中间值之后，左侧部分可能是有序的，也可能是包含旋转点即无序的。如果左侧有序，就判断目标值是否在左侧范围，不在就把左索引移至mid + 1；如果左侧无序，就判断目标值是否在左侧范围，不在就把左索引移至 mid + 1;其他情况（即目标值在左侧范围）就移动右索引至mid；这样不断夹逼，头尾两个索引位会不断逼近目标值，直到他们相遇，此时目标值也好判断了。js要考虑特殊情况，因为最后推到只有两个元素时，算出来的mid是0；这时直接判断两个元素是否匹配就可以了，不纠结！

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    var lo = 0,hi = nums.length -1;
    while(lo < hi){
        var mid = parseInt((lo + hi)/2);
        if(nums[mid] === target) return mid;
        if(nums[mid + 1] === target) return mid+1;
        if(nums[0] < nums[mid] && (target > nums[mid] || target < nums[0])){
            lo = mid + 1;
        } else if (target > nums[mid]&&target < nums[0]){
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return nums[lo] == target ? lo : -1;
};

复杂度分析

时间复杂度： 由于每次都会砍掉当前元素的一半，最终逼近目标值，这个复杂度就是O(logn)

空间复杂度： 由于mid每次遍历都会变，所以这个只能每次都存下来，这个复杂度也是O(logn)

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array