二十分钟入门二分查找
今天介绍下二分查找这个算法套路，学会此招，你的内力会精进三分，与路边程序员能立马拉开差距！
题目描述
整数数组 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
希望对你有帮助，如果有用就请点赞分享在看，谢谢鼓励！