CODEWITHSUNDEEP
javascriptalgorithmbinary-search
Darlyn
Darlyn

Reputation: 4938

Deciding the index of insertion

What is the key point in deciding where to insert an element using binary search ?

Using binary search when the element is present returns its index.

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)

Here I can use splice to insert element on index 1, but what if do

var x = vector.insert(7);

7 isn't present in the array but should be inserted on 2th index.

How could I determine that ?

Upvotes: 0

Views: 129

Answers (3)

Jim Mischel
Jim Mischel

Reputation: 134125

Some binary search implementations return the one's complement of the insertion spot when the item isn't found. In your case, the item would be inserted at index 2 if it were found. But since it's not found, you return -3. The caller sees that the return value is less than 0, does a one's complement, and then inserts at that position.

Example:

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)
}

In your code, rather than return -1, do a return ~mid

The reason for using the one's complement rather than the negative index is that if the item you're looking for is smaller than the smallest item in the array, it would have to be inserted at index 0. But if you returned -0, you'd get ... 0. So it's impossible to tell the difference between the item being found at zero and the item needing to be inserted at index 0. One's complement solves that problem because the one's complement of 0 is -1.

Upvotes: 1

PinkTurtle
PinkTurtle

Reputation: 7041

You probably want to insert the element if it's not found inside your array, using splice(). Also I made small edits to your code.

The index of insertion is determined by your mid variable.

    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>');

Upvotes: 1

dlopez
dlopez

Reputation: 995

Try with something like this:

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;
  }
}

Upvotes: 1

Related Questions