确定插入索引

Question

使用二分查找决定在何处插入元素的关键点是什么？

当元素存在时使用二进制搜索returns它的索引。

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

一些二进制搜索实现 return 未找到项目时插入点的补码。在您的情况下，如果找到该项目，它将被插入到索引 2 处。但是因为没有找到，你 return -3。调用者看到return值小于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。但是如果您returned -0，你会得到 ... 0。所以不可能区分在零处找到的项目和需要在索引 0 处插入的项目之间的区别。一个补码解决了这个问题，因为0的补码是-1.

确定插入索引

Deciding the index of insertion

javascript

algorithm

binary-search