查找

静态查找: 数据集合稳定，不需要添加，删除元素的查找操作
– 组织数据宜用线性表结构
– 如果要对关键字排序，折半查找算法或斐波那契查找算法
动态查找：数据集合在查找过程中需要同时添加或删除元素的查找操作
– 二叉排序树，散列表结构

顺序查找

顺序查找/线性查找:从第一个(或者最后一个)记录开始，逐个进行记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功。
—如果查找了所有的记录仍然找不到与给定值相等的关键字，则查找不成功

//方式一
function search(array,key){
	var i;
	for(var i = 0;i<= array.length;i++){
		if(a[i] == key){
			return i;
		}
  }
  return 0;
}
//方式二
function search(array,key){
	var i= array.length;
	a[0] = key;
	while(a[i] != key){
	  i--
  }
  return i;
}

插值查找(按比例查找)

查找方法类似于折半查找，只不过mid的值不再取low和high的中间值，
而是根据查找值在low和hight中间的大概位置确定mid
var mid = low +(high-low)*(num-list[low])/(list[high]-list[low]);
因此插值查找适用于有一定顺序规律的数组
代码链接

斐波那契查找(黄金查找)

同样适用于有一定顺序规律的数组
在折半查找的基础上根据斐波那契数列进行分割。
在斐波那契数列找一个等于略大于查找表中元素个数的数F[k]，
将原查找表扩展为长度为F[k]-1(如果要补充元素，则补充重复最后一个元素，直到满足F[k]-1个元素)
进行斐波那契分割，即F[k]-1个元素分割为前半部分F[k-1]-1个元素，后半部分F[n-2]-1个元素，剩一个做mid
找出要查找的元素在那一部分并递归，直到找到。

代码链接