二十分鐘入門二分查找

今天介紹下二分查找這個算法套路，學會此招，你的內(nèi)力會精進三分，與路邊程序員能立馬拉開差距！

題目描述

整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值 互不相同 。

在傳遞給函數(shù)之前，nums 在預(yù)先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標 從 0 開始 計數(shù)）。例如， [0,1,2,4,5,6,7] 在下標 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。

給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個整數(shù) 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 中的每個值都 獨一無二
• 題目數(shù)據(jù)保證 nums 在預(yù)先未知的某個下標上進行了旋轉(zhuǎn)
• -10^4 <= target <= 10^4

**進階：**你可以設(shè)計一個時間復雜度為 O(log n) 的解決方案嗎？

題解

這題看著簡單，因為常規(guī)解法很容易想到，直接暴力遍歷就可以了。看代碼：

/**
 * @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)，題目中也提到了這個，向我們發(fā)起了挑戰(zhàn)！來看如何接招吧！

先介紹下二分查找這個算法，非常適合這種題目。這是有一定套路的解法，主要就是約定幾個索引位，從數(shù)組兩頭向中間進行夾逼推進，最終找到目標值。而在每次推進過程中都會舍棄掉當前資源中的一半，這樣算下去，最終的時間復雜度就是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

簡單解釋就是，初始變量設(shè)置數(shù)組的一頭一尾的索引位置，然后取其中間位置，這個中間位置就可以將數(shù)組分為兩段，接著去判斷目標值所在的大概位置，同時調(diào)整查找范圍，這樣不斷的排除查找，最終鎖定目標值。

落到此題目中來，原本的一個順序數(shù)組在某個位置旋轉(zhuǎn)了，這樣一來，取了中間值之后，左側(cè)部分可能是有序的，也可能是包含旋轉(zhuǎn)點即無序的。如果左側(cè)有序，就判斷目標值是否在左側(cè)范圍，不在就把左索引移至mid + 1；如果左側(cè)無序，就判斷目標值是否在左側(cè)范圍，不在就把左索引移至 mid + 1;其他情況（即目標值在左側(cè)范圍）就移動右索引至mid；這樣不斷夾逼，頭尾兩個索引位會不斷逼近目標值，直到他們相遇，此時目標值也好判斷了。js要考慮特殊情況，因為最后推到只有兩個元素時，算出來的mid是0；這時直接判斷兩個元素是否匹配就可以了，不糾結(jié)！

/**
 * @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