静态查找算法

静态查找算法：仅对查找表进行查找操作，不改变表

 

一、顺序查找

   算法思想：从表的一端开始，向另一端逐个按给定值kx与关键字进行比较，若找到，查找成功，并返回位置；若检测完毕，仍未找到，返回错误信息。

 

    算法的时间复杂度：o(n)

    优点：对表中数据的存储没有要求，线性链表只能进行顺序查找

    缺点：当n很大时，平均查找长度达，效率低。

 

package com;

public class Find {
public static void main(String args[]){
	//数组
	int find[] = {1,3,6,9,7,5,8};
	int stat = findKey(find,3);
	System.out.println(stat);
	int stat2 = findKeyR(find,78);
	System.out.println(stat2);
}
//顺序查找，从前往后，查找失败返回长度
public static int findKey(int _find[], int key){
	int len = _find.length;
	int i;
	for(i = 0; i < len && _find[i] != key;i++);
	return i;
}
//顺序查找，从后往前，查找失败返回-1
public static int findKeyR(int _find[], int key){
	int len = _find.length;
	int i;
	for(i = len-1; i >= 0 && _find[i] != key;i--);
	return i;
}
}

 

二、折半查找（二分查找 ）

      折半查找是针对有序表的，即表中的数据元素按关键字升序或降序排列的表。

      前提要求：1.必须采用顺序存储结构 2.必须按关键字大小有序排列

      算法的时间复杂度：o(log(n))

      优点：比较次数少，查找速度快，平均性能好;

      缺点：要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

 

      算法思想：

         首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

package com;

public class Search {
public static void main(String args[]){
	//数组
	int find[] = {1,3,6,7,8,12,23};
	int stat = BinarySearch(find,12);
	System.out.println(stat);
}
//折半查找
public static int BinarySearch(int _find[], int key){
	int len = _find.length;
	//设定返回值，失败时返回-1;
	int flag = -1;
	//区间下界
	int low = 0;
	//区间上界
	int high = len-1;
	//中间位置
	int mid;
	while(low <= high){
		mid = (low + high)/2;
		if(_find[mid] < key){
			low = mid + 1;
		}else if(_find[mid] > key){
			high = mid - 1;
		}else{
			flag = mid;
			break;
		}
	}
	return flag;
}
}

 

三、其他查找

 

    插值查找 ：也是针对有序表的，和二分插值的区别是，mid的取值规则

         mid = low+(key-array[low])*(high-low)/(array[high]-array[low])

    平均性能最好，只适合关键字平均分布的表 ，算法的时间复杂度：o(log(n))

 

    分块查找: 又称索引顺序查找，是对顺序查找的改进。

      算法思想：将查找表分为若干个子表，每个子表分块有序，对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。

    （1）首先用给定值key在索引表中检测索引项，以确定所要进行的查找在查找表中的查找分块，索引表关键字有序，可使用折半查找；

    （2）对该分块进行顺序查找。

 

      平均查找长度：索引表的平均长度和子表的平均长度的和。

         m个数据元素，n个子表， 平均查找长度为(m+n/m)/2+1，当m=sqrt（n）时平均长度最小。