顺序查找、二分查找的算法实现

顺序查找：又称线性查找

思想：从静态查找表的一段开始，将给定的的关键字逐一比较，找到关键字就记录表中的位置。如果比较都不想等，则查找不成功。

顺序查找的线性表结构定义：

public class ElemType<T extends Comparable<T>> {
T key;
public   ElemType() {
	key=null;
}
public   ElemType(T data) {
	key=data;
}

}
public clss SeqTable<T extends Comparable<T>>{
	protected ArrayList<ElemType<T>> elem; //数据元素储存空间基址
	protected int length;
	//构造函数，用数组data中的前n个元素初始化顺序表
	public SeqTable(T[] data,int n){}
	//顺序查找
	public int Search_Seq(T key){}
}

实现：

public  SeqTable(T[] data,int n) {
	elem=new ArrayList<ElemType<Comparable<T>>>();
	ElemType<T> e;
	for(int i=0;i<n;i++){
		e=new ElemType<T>(data[i]);
		elem.add(i,e);
	}
	length=n;
}
public int Search_Seq(T key){
	int i;
	ElemType<T> e=new  ElemType<T>(key);
	elem.add(length,e);
	for (int i = 0;elem.get(i).key.compareTo(key)!=0; ++i) 
		if (i<length) 
			return i;
		else return -1;
	
}
	public static void main(String[] args) {
		int key, index;
		Integer[] data = new Integer[] { 34, 44, 43, 12, 53, 55, 73, 64, 77 };
		SeqTable<Integer> ST = new SeqTable<Integer>(data, 9);
		System.out.println("Please input key world:");
		Scanner sc = new Scanner(System.in);
		key = sc.nextInt();
		index=ST.Search_Seq(key);
		if (index==-1) {
			System.out.println("找不到关键字为"+key+"的元素");
		}else {
			System.out.println("关键字为"+key+"的元素在查找表的索引号为"+index);
		}
	}

二分查找又称折半查找

条件：要求线性表的结构为顺序存储

基本思想：在有序表中，取中间的记录作为比较的对象：如果要查找的关键字等于中间记录的关键字，则查找成功。

如果要查找的值小于中间值，则在中间值的左半区查找。如果要查找的值大于中间值，则在中间值的右半区查找。

算法思路：

1.指定第一个元素为low,最后一个元素为high,中间值mid

查找的关键字key和elem.get(mid).key比较，然后分情况：

1. mid恰好等于key  key=elem.get(mid).key
2. key<mid,   key<elem.get(mid).key ,需要修改上界。high=mid-1,重新再查找
   
3. key>mid,   key>elem.get(mid).key ,需要修改下界。low=mid+1,重新再查找
   
4. 直到low>high，表示查找失败。

实现：

public int Search_Bin(T key){      //折半查找的算法
		int low,hight,mid;
		low=0; hight=length-1;
		while(low<=height){
			mid =(low+high)/2;
			if (key.CompareTo(elem.get(mid).key)==0) 
				return mid;
			else if (key.compareTo(elem.get(mid).key)<0) 
				high=mid-1;
			else low=mid+1;
			
		}
		return -1;
		
	}
	public static void main(String[] args) {
		int key,index;
		Integer[] data=new Integer[]{12,13,33,40,45,56,76,64,66,77};
		SeqTable<Integer> ST = new SeqTable<Integer>(data, 9);//初始化顺序表
		System.out.println("Please input key world:");
		Scanner sc = new Scanner(System.in);
		key = sc.nextInt();
		index=ST.Search_Bin(key); //折半查找开始
		if (index==-1) {
			System.out.println("找不到关键字为"+key+"的元素");
		}else {
			System.out.println("关键字为"+key+"的元素在查找表的索引号为"+index);
		}
	}

后面的主函数基本和顺序查找一样，只是查找的算法函数不同。

版权声明：本文为博主原创文章，未经博主允许不得转载。https://mp.csdn.net/postedit/80164934