欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序查找,二分查找,哈希查找的使用方法和总结

程序员文章站 2024-03-19 15:20:04
...

顺序查找

顺序查找是最普通的一种查找方式,它的基本原理:将要查找的元素与从线性表的开始最后每个元素进行逐个比较,看是否有匹配的

话不多说上代码:

public class Demo4 {

	//顺序查找
	static ArrayList<Integer> list=new ArrayList<Integer>();
	
	   public static void main(String[] args) {

		   //填充数组
		   list.add(99);
		   list.add(88);
		   list.add(22);
		   list.add(33);
		   list.add(44);

		  //输出数组
			for(int i:list){
				System.out.print(i+" ");
			}	
			System.out.println();	
				
		   //顺序查找
		   System.out.println(search(88));	   
	   }	   
		
	   //在list中按顺序查找,若成功返回其下标,否则返回-1
		static int search(int a){
			for(int i=0;i<list.size();i++){
				if(a==list.get(i)){
					return i;
				}	
			}
			return -1;
			
		}
}	   

由此看出: 需要查找的数组中的数越多,所需要的时间越多,但平均时间永远都是0毫秒。

二分查找

二分查找是一种非常常用的查找算法,二分查找也叫折半查找
二分查找的前提条件是线性表是有序的,这样每比较一次就可以排除掉一般的数据元素
Java中自带了二分查找算法,所以一般也不需要我们自己去实现二分查找算法。

话不多说上代码:

public class Demo5 {

	//二分查找
	public static void main(String[] args) {
		ArrayList<Integer> list=new ArrayList<Integer>();

		//填充数组;
		list.add(55);
		list.add(22);
		list.add(66);
		list.add(99);
		list.add(33);
		
		//需要查询的数字
		int a=66;
		
		//数组排序 ( Collections是辅助类)
		Collections.sort(list);

		//输出数组
		for(int i:list){
				System.out.print(i+" ");
		}	
			System.out.println();	
			
		//二分查找
		int pos=Collections.binarySearch(list, a);
		System.out.println(pos);
				
	}
}

由此看出: 和顺序查找一样,需要查找的数组中的数越多,所需要的时间越多,但平均时间永远都是0毫秒。因为是折半查找,它的速度会比顺序查找的速度快很多。

哈希查找

哈希是一种映射,哈希表是一种用空间换取时间的做法,哈希查找可以通过“计算”而不是“查找”得到目标地址。

话不多说上代码:

public class Demo6 {

	//哈希查找
	public static void main(String[] args) {
		Map<Integer,Integer> map=new HashMap<Integer,Integer>();
		
		//填充数组
		map.put(1, 11);
		map.put(6, 66);
		map.put(3, 33);
		map.put(5, 55);
		map.put(4, 44);
		
		//输出数组
		Set<Integer> keySet = map.keySet();
		Iterator<Integer> it1 = keySet.iterator();
		while(it1.hasNext()){
			Integer a = it1.next();
		
			System.out.print (a+"-"+map.get(a)+" ");
		}
		System.out.println();
		
		//哈希查找
		System.out.println(map.get(3));
		
	}
}

由此看出:由于是通过计算得到的目标地址,它的查找速度是最快的

总结:顺序查找<二分查找<哈希查找

由于本人还是一个小菜鸟,写博客主要是为了记录学习过程,跟大家一起进步,如果上述文章中,有任何错误的地方,欢迎指出哦~