<返回更多

二分法搜索算法

2022-02-14  今日头条  北美程序员的自我修养
加入收藏

之前说过,二分法算法是一种非常常见的算法。这里大概说说算法的内容。具体算法如果有兴趣,去百度、维基百科,搜搜就都能找到。我就不做搬运工了。这里就我个人的理解,不严谨的说说。

在排序好的一列大小为n的数组A[],找数字num。设left=0,right=n-1:

while(left<=right){

mid = (left + right)/2;

if (A[mid] == num) return mid;

if (A[mid] < num) left = mid + 1;

if (A[mid] > num) right = mid - 1;

}

return -1;

这里面 mid是我们找的中间点。如果正好找到了,那就直接返回不用继续找了。如果num比中间点的数大,那左边就移动到中间点的右边。这样搜索的范围就小了一半。反之,则把右边移到中间点的左边。

最终如果已经搜素过了整个范围,left已经大于right,我们还没有找到num,那就是这个数组里没有这个数。这里我用一个数组里并不存在的index,-1,来表示。

这个看起来简单,但在实际的实现中,还有很多要注意的地方,这个以后有机会再说。

总之,上面已经给出了了最基本的二分法搜索算法:通过每次重新界定左右边界来缩小一半的搜索范围。

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>