对于二分查找的题型

一般的二分

  • LC704 二分查找 简略
  • LC34 在排序数组中查找元素的第一个和最初一个地位 中等

变体：旋转数组

  • LC153 寻找旋转排序数组的最小值 中等
  • LC33 搜寻旋转排序数组 中等

二分通用技巧

最罕用最根底的二分查找，接管一个数组，和一个target目标值，要寻找到这个指标，返回该指标的下标。找不到就返回-1。间接对应LC704的答案

function search(nums: number[], target: number): number {    let left: number = 0, right: number = nums.length - 1    while (left <= right) {        let mid: number = Math.floor(left + (right - left) / 2)        if (nums[mid] < target){            left = mid + 1        } else if (nums[mid] > target){            right = mid - 1        } else if (nums[mid] === target){            return mid        }    }    return -1};

留神点：

  1. 不必 mid = Math.floor((left + right)/2) 的次要起因是怕超出最大值
  2. while里的left<=right而不是单纯的小于，是因为咱们须要搜寻的区域是一个闭区间，也就是[left,right]，这样能力确定不漏掉一个数

然而，有些时候，目标值不止一个，也就是说可能有多个目标值，咱们须要找到其左边界和右边界，所以下面的算法靠不住了，然而仍然能够在下面的算法中做肯定的改变。这里次要学习到的是labuladong的算法秘籍中提到的思路。

假如在一个新的数组中，[1,2,3,3,3,4]，咱们要找target = 3的左右边界，怎么办呢？

这里间接贴LC34里我的解法，超过了98%的同学

//main functionfunction searchRange(nums: number[], target: number): number[] {    return [leftBound(nums,target), rightBound(nums,target)]};//find left boundfunction leftBound(nums: number[], target: number): number {    let left: number = 0, right: number = nums.length - 1    while (left <= right){        let mid: number = Math.floor(left + (right - left)/2)        if (nums[mid] < target){            left = mid + 1        } else if (nums[mid] > target){            right = mid - 1        } else {            right = mid - 1        }    }    //重点局部    if (left >= nums.length || nums[left] !== target) {        return -1    } else {        return left    }}//find right boundfunction rightBound(nums: number[], target: number): number {    let left: number = 0, right: number = nums.length - 1    while (left <= right){        let mid: number = Math.floor(left + (right - left)/2)        if (nums[mid] < target){            left = mid + 1        } else if (nums[mid] > target){            right = mid - 1        } else {            left = mid + 1        }    }    //重点局部    if (right < 0 || nums[right] !== target) {        return -1    } else {        return right    }}

这个题目的意思很简略，就是让咱们找到左右边界而已，那咱们别离去找左边界和右边界就行。仔细观察的话，会发现和根底的差异不大，然而多进去两行判断后果的局部。而后在nums[mid] === target 的时候，咱们没有去输入，而是放大边界持续查找。

重点的局部，在于了解，什么时候会跳出循环，咱们给定的条件是left <= right， 因而，当left > right 的时候，就能够跳出循环。

先思考leftBound这个函数，当nums[mid]正好等于左边界的时候，咱们的right再次放大范畴到左边界-1的地位，此之后的left会不停的增大直到和right相等，最初left = mid + 1 便刚刚好大于right，且等于左边界的地位。

跳出循环之后，再次进行判断，因为咱们没有思考两种极其状况，一种是left超过边界，一种是找到的左边界并不等于target，这样算进去的后果就是正确的。

旋转数组：二分查找的变体

在leetcode中，有不少旋转数组的题，这里挑两个聊聊。一个是LC153的最根底的旋转数组。像是[3,4,5,0,1,2]就是典型的旋转数组，咱们能够发现法则，就是除了两头一个点是无序的，其余的都是有序的，那咱们是不是通过二分查找能够去找到这个旋转点呢？（有的同学抉择间接遍历，也不是不行，就是在数据量微小的时候，工夫复杂度很高）在这个题目中，咱们只有输入0就能够，也就是所说的旋转点。间接贴答案

function findMin(nums: number[]): number {    let left: number = 0, right: number = nums.length - 1    while (left < right){        let mid: number = Math.floor(left + (right - left) /2)        if (nums[mid] < nums[right]){            right = mid        } else if (nums[mid] > nums[right]){            left = mid + 1        }    }    return nums[left]};

这里又呈现了一个比拟坑的点，为什么是left < right呢，一个等号区别这么大吗？ 我试过改为小于等于，再改点其余中央七七八八，发现都得不到正确的后果。咱来仔细分析一下起因。

之前说过一个问题，那就是判断循环的进口条件，这里的话就是left === right，循环就完结了，咱们想找到的旋转点是最小值，所以当咱们在mid刚好是旋转点时，必定是进入的第一个判断。

为什么呢？为什么我能确定mid肯定比此时的right小呢，第一个起因是Math.floor，mid跟right相等的惟一条件是left === right，就退出循环了。所以咱们下一步失去的是mid = 旋转点 - 1，此时对应的数值是最大值，所以必定比方才的right大，而后left和right相等，退出循环，返回left和right皆可。

所以说二分查找，如果要探讨的十分粗疏的话，边界条件是思考的非常复杂的。

最初看一个题，是LC33，搜寻旋转排序数组，其实就是把旋转数组和二分查找的经典模版联合而已。

function search(nums: number[], target: number): number {    const spin = findSpinIndex(nums)    if (target < nums[spin] || target > nums[spin - 1]) {        return -1    } else if (target > nums[nums.length - 1]){        return binarySearch(nums, target, 0, spin - 1)    } else if (target <= nums[nums.length - 1]){        return binarySearch(nums, target, spin, nums.length - 1)    }};function findSpinIndex(nums:number[]): number {    let left: number = 0, right: number = nums.length - 1    while (left < right){        let mid: number = Math.floor(left + (right - left) / 2)        if (nums[mid] < nums[right]){            right = mid        } else if (nums[mid] > nums[right]){            left = mid + 1        }    }    return left}function binarySearch(nums: number[], target: number, leftBound: number, rightBound: number): number {    let left: number = leftBound, right: number = rightBound    while (left <= right){        let mid: number = Math.floor(left + (right - left) / 2)        if (nums[mid] > target){            right = mid - 1        } else if (nums[mid] < target){            left = mid + 1        } else if (nums[mid] === target) {            return mid        }    }     return -1 }

这个题没什么特地须要留神的中央，留神一下主函数的边界判断就好