挿入インデックスの決定

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やっていることは、アレイに存在していないが、2番目のインデックスに挿入されるべきことができます。

どうすれば決定できますか？

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

項目が見つからない場合、一部のバイナリ検索の実装は、挿入スポットの1の補数を返します。あなたのケースでは、アイテムが見つかった場合、そのアイテムはインデックス2に挿入されます。しかし、それが見つからないので、あなたは-3を返します。呼び出し元は、戻り値が0より小さく、1の補数をしてから、その位置に挿入することを確認します。

例：

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

負のインデックスではなく、1の補数を使用した理由は、もしあなたが探しているアイテム配列内の最小の項目よりも小さい場合は、インデックス0に挿入する必要があります。しかし、-0を返した場合は、0になります。したがって、見つかった項目の差異をゼロ索引0に挿入する必要がある項目を示します。1の補数は、その問題を解決します。 0は-1です。