几种常见的查找方法

最近在看查找算法，所以就总结一下：
1、顺序查找（sequential search）是一种最简单的查找方法，一般用于数组。他从顺序表的一端开始依次将每个元素值同给定的值进行比较，若找到则返回该元素所在的下标；否则返回特定值，表示查找失败。时间复杂度O（n)。
对顺序查找算法的一个改进，可在表的尾端设置一个“岗哨”，即在查找之前把给定值x赋给数组a[]中下标为n的元素，这样在循环中就不必进行下标是否越界的检查，当比到下标为n的元素位置时，由于a[n]=x必然成立，则退出循环。即

a[n]=x;
	for(int i=0;;i++)
	 if(a[n].equals(x)) break;

2、二分查找（binary search）又称折半查找。作为二分查找对象的数据必须是顺序存储的有序表，通常假设若关键字是字符或者字符串数据，则按照国际双字节编码（Unicode）有序。
二分查找的过程是：首先取整个有序表的中点元素，同x比较，若小于给定值则在坐子表中，否则在有子表中；这样经过依次查找就将缩短一半的查找空间，直到找到x元素或者当前查找元素为空。
算法描述：

public class testSearch {
	public static int binarySearch(Object []a,Object x,int n){
		//从数组a的前n个元素中二分查找给定值x
		int low=0,high=n-1;
		while(low<=high){
			int mid=(low+high)/2;
			if(((Comparable)a[mid]).compareTo(x)>0)
			{
				high=mid-1;
				System.out.print(a[mid]);
			}
			else if(((Comparable)a[mid]).compareTo(x)<0){
				low=mid+1;

				System.out.print(a[mid]);
			}
			else{

				System.out.print(a[mid]);
				return mid;
			}
		}
		return -1;//未返回mid则表明查找失败，返回-1
	}
	public static void main(String[] args) {
		Object[]a={1,2,3,4,5,6,7,8,9};
		testSearch.binarySearch(a, 1, a.length);
		
	}
}

二分查找过程可用一颗二叉树来描述：树中的每个根节点对应当前查找区间的中点元素a[mid]，它的左子树和右子树分别对应该区间的坐子表和右子表，通常把此二叉树称为二分查找的判定树。进行二分查找的二叉树是一颗二叉搜索树，而且是一颗理想平衡树。
二分查找的时间复杂度是O（log2 n）。
3、索引查找（index search）又称分级查找。索引查找是在索引表和主表上进行的查找，过程为：首先根据给定的索引值K1，在索引表上查找索引值等于K1的索引项，以确定对应子表在主表中的开始位置和长度，然后再根据给定值K2，在对应的子表中查找等于K2的元素。对索引表或者子表进行查找时，若表是顺序存储的有序表，则既可以进行顺序查找也可以进行二分查找。
4、分块查找（blocking search）属于索引查找。他要求每个主表中每个子表之间递增有序，即前块中的最大关键字必须小于后块中的最小关键字，但是每个块中的元素排列次序可以是任意的。进行分块查找时，应根据所给的关键字首先查找索引表，从中查找刚好大于等于所给关键字的那个索引项，从而找到待查块，然后再查找这个块，从中顺序查找到相应的记录。
5.散列查找
散列（hash)存储的方法是：以数据集合中的每个元素的关键字k为自变量，通过一种函数h(k)计算出函数值，把这个值用作一块连续存储空间中的元素存储位置（下标）。
构造散列函数的目标是使得散列地址尽可能均匀地分布在散列地址的空间上，同时使得计算尽可能简单，以节省计算时间。常用的散列函数有：
直接定址法 h(k)=k+C;
除留余数法 h(k)=k%m，m是散列长度
数字分析法 取关键字中某些取值较分散的数字作为散列地址的方法。
平方取中法 取关键字平方的中间几位作为散列地址的方法。
折叠法  首先将关键字分割成位数相同的几段（最后一段的位数不足应补0），段的位数取决于散列地址的位数，然后将他们的叠加和作（舍去最高位进位）为散列地址的方法。
从散列表中查找关键字为key的过程就是一个按照查找路径进行顺序查找的过程，若找到则返回相应的元素值，否则返回空值表示查找失败。
6.B树查找
B树是一种具有特殊结构的树，他同二叉树和一般树在结点结构上有所不同。B树分为B-树和B+树。
B_树是一种特殊的多叉树，被称为多路查找树。B_树是一中在数据库和文件系统中最常用的动态索引结构。对于树根节点他最少有两颗子树，最多有m棵子树，对于非树根节点，他最少有m/2向上取整棵子树，最多m棵子树，叶子结点中的子树均为空树；每个节点的关键字个数最少为m/2向上取整-1，最多为m-1个；在B_树的结点结构中，每个关键字域的后面还应包含一个元素引用域，用以存储该关键字所对应元素的引用。
B_树的查找一个关键字K的过程：若B_树非空，首先取出树根结点，使给定值K依次同该结点中的每一个关键字进行比较，直到K<=Ki(假定用Ki作为终止标志，保存比所有关键字都大的一个特定值，该值不妨用MaxKey常量表示)为止，此时若K=Ki，则表明查找成功，返回具有该关键字Ki的记录的存储位置，否则其值为K的关键字只能落在该结点的有Pi-1所指的子树上，接着只要在该子树上继续进行查找即可；这样，每取出一个节点比较后就下移一层，直到查找成功，或被查找的子树为空为止。

public int search(Object k){
		int i;
		BayerTreeNode p=bt;//将树根指针bt赋给p
		while(p!=null){
			i=1;
			while(((Comparable)k).compareTo(p.key[i])>0)
				i++;//用k顺序同节点关键字比较
			if(((Comparable)k).compareTo(p.key[i])==0)
				return p.rec[i];//查找成功返回记录的存储位置
			else
				p=p.ptr[i-1];//否则继续向下层节点找
		}
		return -1;
	}