JavaScript数据结构22—简单的查找算法

以下算法包括了

1. 顺序查找

• 插值查找
• 二分查找
• 斐波那契查找

//查找算法
//顺序表查找
Array.prototype.sequential_search = function(key) {
  var count = 0;
  for (var i = 0; i < this.length; i++) {
    count++;
    if(this[i]==key){
      return {index:i,count:count};
    }
  }
  return -1;
}
//有序表查找
Array.prototype.binary_search = function(key){
  var low = 0;
  var high = this.length - 1;
  var mid,count = 0;
  while(low<=high){
    count++;
    mid = parseInt((low+high)/2);
    if(key<this[mid]){
      high = mid-1;
    }else if(key>this[mid]){
      low = mid+1;
    }else{
      return {index:mid,count:count}
    }
  }
}
//插值查找
Array.prototype.insert_search = function(key){
  var low = 0;
  var high = this.length - 1;
  var mid,count = 0;
  while(low<=high){
    count++;
    mid = low + parseInt((high-low)*(key-this[low])/(this[high]-this[low]));
    if(key<this[mid]){
      high = mid-1;
    }else if(key>this[mid]){
      low = mid+1;
    }else{
      return {index:mid,count:count}
    }
  }
}
//斐波那契查找 原理 F[K]-1 = F[K-1]-1+F[K-2]-1  +  1
Array.prototype.fibonacci_search = function(key){
  function F(k){
    if(k==0||k==1){
      return k;
    }
    if(k==2){
      return 1;
    }
    var a=1,b=1,res;
    for(var i=3;i<=k;i++){
        res = a + b;
        a = b;
        b = res;
    }
    return res;
  }
  var low = 0;
  var high = this.length - 1;
  var k = 0,count = 0;
  while(this.length>F(k)){
    k++;
    count++;
  }
  for (var i = this.length; i < F(k)-1; i++) {
    this[i] = this[this.length-1];
    count++;
  }
  while(low<=high){
    count++;
    mid = low+F(k-1)-1;
    if(key<this[mid]){
      high = mid-1;
      k = k - 1;
    }else if(key>this[mid]){
      low = mid+1;
      k = k-2;
    }else{
      if(mid<=this.length){
        return {index:mid,count:count};
      }else{
        return -1;
      }
    }
  }
  return 0 ;
}
var array1 = [];
var array1Index = 0
for (var i = 0; i < 1000; i++) {
  array1Index += parseInt(Math.random()*10)+1;
  array1[i] = array1Index;
}
console.info(array1);
console.info(array1.binary_search(array1[5]));
console.info(array1.sequential_search(array1[5]));
console.info(array1.insert_search(array1[5]));
console.info(array1.fibonacci_search(array1[5]));

输出

{ index: 5, count: 10 }
{ index: 5, count: 6 }
{ index: 5, count: 3 }
{ index: 5, count: 627 }
[Finished in 0.1s]