关于二分查找:typescript二分查找算法进阶总结包括旋转数组

对于二分查找的题型

一般的二分

• 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 function
function searchRange(nums: number[], target: number): number[] {
    return [leftBound(nums,target), rightBound(nums,target)]
};

//find left bound
function 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 bound
function 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 
}

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