欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找思想及代码

程序员文章站 2024-03-20 09:15:52
...

思想:

1:从有序数组的中间元素开始查找,如果该元素正好是查找的值,则查找结束,否则进行下一步;

2:如果指定要查找的元素大于或小于中间元素,则在数组大于或小于中间元素的那一半查找,然后重复第一步;

3:重复以上过程,直到找到目标元素的索引,查找成功,或直到查到子数组为空,查找失败。

代码:

function search(arr,item){
    var low =0; //最低位置
    var high = arr.length-1; //最高位置
    while(low<=high){
        var mid = Math.floor((low+high)/2); //向下取整,获取中间值的位置
        if(arr[mid] === item){ //是的话直接返回
            return mid;
        }
        else if(arr[mid]<item){
            low = mid+1; //此时最低位,就是mid+1
        }else{
            high = mid-1; //此时最高位,就是mid-1
        }
    }
    return false;
}
var arr = [1,2,3,4,5,6];
var item = 4;
console.log(search(arr,item));