关于前端:二分搜索算法

45次阅读

共计 561 个字符,预计需要花费 2 分钟才能阅读完成。

二分搜寻

原文链接:https://note.noxussj.top/?source=sifo

什么是二分搜寻?

二分搜寻是一种比拟高效的搜索算法,但前提必须是有序数组。次要步骤如下:

  1. 从数组的两头元素开始,如果两头元素正好是目标值,则搜寻完结
  2. 如果目标值大于或者小于两头元素,则在大于或者小于两头元素的那一半数组中持续二分搜寻

根底案例

  • 工夫复杂度:O (logn)
  • 空间复杂度:O (1)
    Array.prototype.binarySearch = function (target) {
        let low = 0
        let high = this.length - 1
    
        while (low <= high) {const mid = Math.floor((low + high) / 2)
            const element = this[mid]
    
            if (element < target) {low = mid + 1} else if (element > target) {high = mid - 1} else {return mid}
        }
    
        return -1
    }
    
    const res = [1, 2, 3, 4, 5].binarySearch(1) // 0

因为每次比拟都使搜寻范畴放大一半,所以工夫复杂度是 O (logn)。而空间复杂度是 O (1),因为没有应用线性增长的变量。


原文链接:https://note.noxussj.top/?source=sifo

正文完
 0