Open xszi opened 3 years ago
二分查找也称折半查找算法,它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字,让你猜我写的是什么?你每猜一次,我就会告诉你猜的大了还是小了,直到猜中为止。
该算法要求待查找的数组已排序,实现步骤如下:
function binarySearch(items, item) { var low = 0, high = items.length - 1, mid, elem while(low <= high) { mid = Math.floor((low+high)/2) elem = items[mid] if(elem < item) { low = mid + 1 } else if(elem > item) { high = mid - 1 } else { return mid } } return -1 }
二分查找易错点:
low <= high
mid
Math.floor((low+high)/2)
low high
low = mid + 1 high = mid - 1
二分查找局限性:
复杂度:
二分查找也称折半查找算法,它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字,让你猜我写的是什么?你每猜一次,我就会告诉你猜的大了还是小了,直到猜中为止。
该算法要求待查找的数组已排序,实现步骤如下:
二分查找易错点:
low <= high
,注意是 <=mid
的取值是Math.floor((low+high)/2)
low high
每次更新的时候,low = mid + 1 high = mid - 1
二分查找局限性:
复杂度: