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

45次阅读

共计 3686 个字符，预计需要花费 10 分钟才能阅读完成。

一般的二分

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
};

留神点：

不必 mid = Math.floor((left + right)/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 
}

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

正文完