Milis to seconds二进制搜索

Question

我只是在练习二进制搜索算法，我想知道以秒为单位需要多少时间才能完成。

我对待startMilis和endMilis的方式是获得时间度量的正确方式吗？谢谢。

let ar = [3,4,6,7,4,3,2,1,5,8,7,6,4,3,5,6,7,8,9];

console.log(binarySearch(ar, 7));

function binarySearch(arr, value){
    let startMilis = Date.now();
    let endMilis = 0;

    let sorted = arr.sort((a,b)=>{return a-b;});    
    let high = sorted.length-1;
    let low = 0;
    let mid = 0;

    //console.log("input array sorted to: "+sorted);

    while(low <= high){
        mid = Math.floor( (low+high)/2 );
        
        if(sorted[mid] == value){
            endMilis = Date.now();
            return `${value} found at index: ${mid} in ${(endMilis-startMilis)/1000} seconds`;
        }
        else if(sorted[mid] < value) low = mid+1;
        else if(sorted[mid] > value) high = mid-1;
    }

    endMilis = Date.now();
    return "The requested value was not found, duration: "+(endMilis-startMilis)/1000+" seconds";
}

Answer 1

如果您想测量特定函数的性能，请将其与分析代码包装在一起，以获得无偏差的结果。例如：

console.time('binarySearch');
binarySearch(ar, 7)
console.timeEnd('binarySearch');

我在这里推荐的另一件事是分离关注点。您的函数应该只返回一个找到的值(对于“未找到”的情况，还要返回一些特殊的值)，仅此而已。记录某些指标(如速度、内存等)不应附加到该返回值。

有了这种方法，使用特定于平台的分析工具(甚至像console.time/timeLog/timeEnd一样简单)来实现它们的唯一目的-分析将会容易得多。

顺便说一句，您实际上不应该对源数组进行排序，因为它是就地排序；除非有很强的理由，否则您应该避免修改函数参数等副作用。

Answer 2

可以，但您也可以将开始点和结束点放在函数之外，这样就不必担心处理所有返回

let ar = [3,4,6,7,4,3,2,1,5,8,7,6,4,3,5,6,7,8,9];

let startMilis = Date.now();
console.log(binarySearch(ar, 7));
let endMilis = Date.now();
console.log("search duration: "+(endMilis-startMilis)/1000); 

function binarySearch(arr, value){

let sorted = arr.sort((a,b)=>{return a-b;});    
let high = sorted.length-1;
let low = 0;
let mid = 0;

//console.log("input array sorted to: "+sorted);

while(low <= high){
    mid = Math.floor( (low+high)/2 );
    
    if(sorted[mid] == value){
        return `${value} found at index: ${mid}`;
    }
    else if(sorted[mid] < value) low = mid+1;
    else if(sorted[mid] > value) high = mid-1;
}
return "The requested value was not found";

}