確定插入索引

Question

決定使用二分搜索插入元素的位置的關鍵點是什麼？

元素存在時使用二進制搜索返回其索引。

function arr() { 
    this.arr = [5, 6, 8]; 
    this.insert = function(element) { 
    var low = 0; 
    var high = this.arr.length - 1; 
    while (low <= high) { 

     var mid = parseInt((low + high)/2); 
     if (element == this.arr[mid]) { 
     return mid; 
     } else if (element > this.arr[mid]) { 
     low = mid + 1; 
     } else { 
     high = mid - 1 
     } 
    } 
    return -1 
    } 
} 
var vector = new arr(); 
var x = vector.insert(6); // return 1 
alert(x) 

在這裏，我可以使用拼接到索引1插入元件，但如果這樣做

var x = vector.insert(7); 

7不存在於陣列中的，但應該在二路索引被插入。

我怎麼能確定？

Answer 1

嘗試用這樣的事情：

function arr() { 
    this.arr = [5, 6, 8]; 
    this.insert = function(element) { 
    var low = 0; 
    var high = this.arr.length - 1; 
    while (low <= high) { 

     var mid = parseInt((low + high)/2); 
     if (element == this.arr[mid]) { 
     return mid; 
     } else if (element > this.arr[mid]) { 
     low = mid + 1; 
     } else { 
     high = mid - 1 
     } 
    } 
    return mid; 
    } 
} 

Answer 2

你可能要插入的元素，如果它不是你的陣列裏發現，使用splice()。我還對你的代碼做了小小的修改。

插入索引取決於您的mid變量。

function arr() { 
 
     this.arr = [5, 6, 8]; 
 
     this.insert = function(element) { 
 
     var low = 0; 
 
     var high = this.arr.length; 
 
     while (low <= high) { 
 

 
      var mid = Math.floor((low + high)/2); 
 
      if (element == this.arr[mid]) { 
 
      return mid; 
 
      } else if (element > this.arr[mid]) { 
 
      low = mid + 1; 
 
      } else { 
 
      high = mid - 1; 
 
      } 
 
     } 
 
     this.arr.splice(mid, 0, element); 
 
     return mid; 
 
     } 
 
    } 
 

 
    var vector = new arr(); 
 

 
    var x = vector.insert(6); 
 
    console.log(x); // 1 
 

 
    var x = vector.insert(7); 
 
    console.log(x); // 2 
 

 
    var x = vector.insert(9); 
 
    console.log(x); // 4 
 

 
    console.log(vector.arr); // Array [ 5, 6, 7, 8, 9 ] 
 

 
    document.write('<p>Check your console :-)</p>');

Answer 3

一些二進制搜索實現返回插入點的一個補時未找到該項目。在你的情況下，該項目將被插入索引2，如果它被發現。但是，因爲沒有找到，你會返回-3。調用者看到返回值小於0，做一個補碼，然後插入該位置。

例子：

result = find(7)  // find the value in the array 
if (result < 0)  // if not found 
{ 
    index = ~result // complement the result 
    insert(7, index) // and insert (probably using splice) 
} 

在你的代碼，而不是return -1，做一個return ~mid

之所以使用一補，而不是負折射率的是，如果你正在尋找的項目小於數組中的最小項，它將不得不插入到索引0處。但是，如果您返回-0，則會得到... 0.因此，無法分辨出找到的項爲零以及需要插入索引0的項目。由於補碼的補碼，補碼解決了該問題0是-1。