常见查找算法

查找简单理解即为在集合中查询获取需要的元素，不同的查询条件以及集合中数据的存储方式决定了使用不同的查找方法。

查找的分类

静态查找：只查找，不改变集合内的数据元素，例如：顺序查找，二分查找，分块查找

动态查找：既查找，又改变集合（增删）内的数据元素，例如：二叉树查找

1、顺序查找

又称线性查找，是从数组的第一个元素开始查找，直到找到待查找元素的位置，直到查找到结果。最佳的状况时间是1，就是第一个就是待查找的远射，最差的查找状况是O（n），就是最后一个是待查找的元素。

算法思路：给定一个key值，在数组中顺序对比，若存在k=key，则查找成功，返回数组中该元素下标，失败返回-1；

int order(int[] array, int tar) {
			for (int i = 0; i < array.length; i++) {
				if (tar == array[i])
					return i + 1;
			}
			return -1;
	}

2、二分查找

又称折半查找，是将待查找的数组元素不断的分为两部分，每次淘汰二分之一，但是有个大前提是，元素必须是有序的，如果是无序的则要先进行排序操作，这种查找的方法，类似于找英文字典的Java，我们可以一下子找到字母J开头的，再仔细找。最佳的状况时间是1，就是第一次分开就查找到了，最差的查找状态是O（n），便是待查找的数据出现在最后一次。

前提:元素必须是有序的，如果是无序的则要先进行排序操作

二分法查找递归实现

public class testBinaryOne {

	
public static Integer testBinarySearch(int[] a,int key,int low,int high){
	
		if(low > high){
			return -1;
		}
		
		while(low <= high){
			int mid = (low + high)/2;
			if(key == a[mid]){
				return mid;
			}else if(key < a[mid]){
				return testBinarySearch(a,key,low,mid-1);
			}else{
				return testBinarySearch(a,key,mid+1,high);
			}
		}
		
		return -1;
	}
	
	
	
	
	public static void main(String[] args){
		int[] a = {1,3,5,7,9,11,13,16,22,55};
		Integer mm = testBinarySearch(a, 16,0,a.length);
		System.out.println("16的位置在："+ mm +"位");
	}
}

二分法查找非递归实现

public class TestSearch {

	
	public static Integer testBinarySearch(int[] a,int key){
		
		int low = 0;
		int high = a.length;
	
		if(low > high){
			return -1;
		}
		
		while(low <= high){
			int mid = (low + high)/2;
			if(key == a[mid]){
				return mid;
			}else if(key < a[mid]){
				high = mid - 1;
			}else{
				low = mid + 1;
			}
		}
		
		return -1;
	}
	
	
	
	
	public static void main(String[] args){
		int[] a = {1,3,5,7,9,11,13,16,22,55};
		Integer mm = testBinarySearch(a, 16);
		System.out.println("16的位置在："+ mm +"位");
	}
}

3、分块查找

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

一、先选取各块中的最大关键字构成一个索引表；

二、查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；

然后，在已确定的块中用顺序法进行查找。

typedef int keytype;
	 
	    typedef struct {
	        keytype Key;
	    }elemtype;
	 
	    typedef struct{
	        keytype Key;
	        int Link;
	    }indextype;
	 
	    /**
	     * 分块查找关键字为Key的记录。索引表为ls[0]-ls[m-1],顺序表为s，块长为l
	     */
	    int IndexSequelSearch(indextype ls[],elemtypes[],int m,int l,keytype Key){
	        int i,j;
	        /*在索引表中顺序查找*/
	        i=0;
	        while(i<m&&Key>ls[i].Key)i++;
	     
	        if(i>=m)
	            return -1;
	        else{
	            /*在顺序表中顺序查找*/
	            j=ls[i].Links;
	            while(Key!=s[j].Key&&j-ls[i].Link<l)
	                j++;
	     
	            if(Key==s[j].Key)
	                return j;
	            else
	                return -1;
	        }
	    }

4、二叉树查找

二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。

这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

// 二叉树递归查找算法
BinaryTreeNode binaryTreeRecusion(BinaryTreeNode bt, Object tar) { 
		if (bt == null)
			return new BinaryTreeNode("null");
		switch (strategy.compare(tar, bt.getData())) {
		case -1:// tar比data小就查找左子树
			return binaryTreeRecusion(bt.getLeftChild(), tar);
		case 1:// tar比data大就查找右子树
			return binaryTreeRecusion(bt.getRightChild(), tar);
		default:// 比较结果是0，tar和data相等就返回
			return bt;
		}
	}
    
    // 二叉树非递归查找算法
	BinaryTreeNode binaryTree(BinaryTreeNode bt, Object tar) { 
		while (bt != null) {
			switch (strategy.compare(tar, bt.getData())) {
			case -1:// tar比data小就查找左子树
				return bt = bt.getLeftChild();
			case 1:// tar比data大就查找右子树
				return bt = bt.getRightChild();
			default:// 比较结果是0，tar和data相等就返回
				return bt;
			}
		}
		return new BinaryTreeNode("null");
}