猫史档案馆

[算法原理]

中分（划掉 二分查找是在一个序列中查找某元素的算法，但仅限排序过的序列。

原理是在固定范围内选择中间的元素，和目标元素比较，并根据结果来缩小范围或者返回值。

[算法模拟]

比如说，有一个序列[1,5,6,11,15,78,99,100,254,514,1919]，我们要在这个序列中去查找514的索引（悲

以下红色为选中的元素，[]为固定范围。

[1,5,6,11,15,79,99,100,254,514,1919]

79<514

1,5,6,11,15,79,[99,100,254,514,1919]

254<514

1,5,6,11,15,79,99,100,254,[514,1919]

514==514

返回514索引：9（0为第1个）

[代码]

这里只展示JS了：

let a=[1,5,6,11,15,78,99,100,254,514,1919]
var mn=0,mx=10,mid=5
while(true){
    mid = mn+((mx-mn+1)+(mx-mn+1)%2)/2
    if (a[mid]==514){
        console.log(mid)
        break
    }
    if (a[mid]<514){
        mn=mid+1
        continue
    }
    if (a[mid]>514){
        mx=mid-1
        continue
    }
}

[算法优点]

在面对大量数据时，二分查找比普遍查找（指循环遍历）要快很多，普遍查找时间复杂度为O(n)，二分查找则是O(log2n),log2n指的是以2为底n的对数。

有任何不懂的地方可以问帖主