用js实现二分查找法二分查找法

150 阅读 0 评论 99 点赞

我是靠谱客的博主辛勤鸵鸟，这篇文章主要介绍用js实现二分查找法二分查找法，现在分享给大家，希望可以做个参考。

二分查找法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

function binarySearch(arr, target){

    let start = 0;
    let end = arr.length - 1;
    if(!end){
		return arr[0] === target ? 0 : -1;		
	}
    if(end == 1){
        return arr[0] === target ? 0 : arr[1] === target ? 1 : -1; 
    }
    let middle;
    while(start <= end){
        middle = (start + end) / 2 | 0; // 向下取整
        if(arr[middle] === target){
            return middle
        }else if(target > arr[middle]){
            start = middle + 1
        }else{
            end = middle - 1
        }
    }
    return -1
}