binarySearch二分查找——Javascript实现

时间:2023-03-08 16:33:52

在很早之前,我就写过了一篇也关于二分法的相关博文:JavaScript快排与原生sort的测试。当时是用二分法进行快速排序,其实和这次思路大致相当。二分查找最重要的一个条件,就是需要将数组是有序的方可进行查找,这里更多的是从小到大的排列顺序。

一起来想想大致的思路:

1. binarySearch函数需要接收的参数是:一个预先排序好的数组,一个需要查找的目标值,左边界和右边界。
2. 让数组的中值和目标值比较,若相等,则返回中值所在的序号,函数结束。若不相等,进行第三步
3. 不相等,则进行大小比较,若目标比中值小,则范围缩小到左边界到中值,并重新返回第一步。反之,范围缩小到中值到右边界,返回第一步。
4. 找不到则是,中值序号等于左边界或右边界,返回-1。
function bSearch(arr, target, start = 0, end = arr.length - 1) {
const midIndex = Math.ceil((start + end) / 2)
const midValue = arr[midIndex] if(target === midValue) return midIndex
if(start === midIndex || end === midIndex) return -1
if(target < midValue) return bSearch(arr, target, start, midIndex - 1)
if(target > midValue) return bSearch(arr, target, midIndex + 1, end)
}