插入點的二進制搜索 - 爲什麼插入點錯誤？

大家好，感謝您的時間！我實現一個簡單的二進制搜索算法下面的JS代碼：插入點的二進制搜索 - 爲什麼插入點錯誤？

function binarySearch(arrayWhereSearching , searchElement , comparePropertyOfArrayWhereSearching , comparePropertyOfSearchElement) 
{ 
    var minIndex = 0 ; 
    var maxIndex = arrayWhereSearching.length - 1 ; 
    var currentIndex ; 
    var currentElement ; 

    while(minIndex <= maxIndex) 
    { 
     currentIndex = (minIndex + maxIndex)/2 | 0 ; 
     currentElement = arrayWhereSearching[currentIndex] ; 

     if(currentElement[comparePropertyOfArrayWhereSearching] < searchElement[comparePropertyOfSearchElement]) 
     { 
      minIndex = currentIndex + 1 ; 
     } 
     else if(currentElement[comparePropertyOfArrayWhereSearching] > searchElement[comparePropertyOfSearchElement]) 
     { 
      maxIndex = currentIndex - 1 ; 
     } 
     else 
     { 
      return currentIndex ; 
     } 
    } 

    return ~currentIndex ; 
}

如果，例如，我測試的算法，看看我得到2的補插入點時的值不爲數組，我得到錯誤的值。例如：

var ar = [ {value: 1} , {value: 2} , {value: 5} , {value: 9} , {value: 11} , {value: 13}] ; 

binaryIndexOfSafehubDevice(ar , {value: 14} , "value" , "value") ; // return -6, which 5 in 2's complement. But I was expecting the index 6.

我在想什麼？

來源

2017-08-29 Alessio Vallero

將最終的退貨聲明更改爲~minIndex它應該可以解決您的問題。

currentIndex沒有關於該元素是否會在該索引之後或之前出現的信息。但是，如果搜索元素較大，則minIndex將增加，如果元素較小，則保持不變。

來源

2017-08-29 21:13:59

爲什麼使用按位NOT？ – Bergi

之後就可以簡單地檢查'currentIndex <0'來查看它是否找到了該元素。否則，它可以〜（按位不）返回找到插入索引。儘管你可以輕而易舉地否定它。 –

澄清，否定因爲0而不起作用。但是按位或或者尊重屬性〜x = 0，允許您存儲取反的插入位置並僅用1個返回值檢查算法是否成功。 –

插入點的二進制搜索 - 爲什麼插入點錯誤？

回答

相關問題