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

查找(一)-----顺序表的顺序查找和折半查找

程序员文章站 2022-03-15 11:40:36
...

顺序表的顺序查找:

基于顺序表,查找指定的key元素, 给出三种:返回它的索引值(否则返回-1), 判断是否存在这个值(存在返回true, 否则false),查找(存在返回这个元素的值, 不存在返回-1)。就是对这个顺序表进行遍历。从第一个元素开始和指定的元素做比较。

参考代码:

public class SeqSearch<T> {

	public static void main(String[] args) {

		SeqSearch<String> seq = new SeqSearch<String>();
		seq.init("one");
		seq.init("two");
		seq.init("three");
	    seq.init("four");
		System.out.println(seq.contains("4"));
		System.out.println(seq.indexOf("three"));
		System.out.println(seq.search("two"));
	}
		
	private int DEFAULT_SIZE = 20;
    private Object[] elements;
	private int length;
	
	private int j;

	public SeqSearch(){
		this.length = DEFAULT_SIZE;
		elements = new Object[length];
	}
	
	public SeqSearch(int size){
		this.length = size;
		this.elements = new Object[length];
	}
	
	public void init(T data){ 
		if(j > length - 1){
			throw new IndexOutOfBoundsException("数组已满!");
		}
		elements[j ++] = data;
	}
	
	public int indexOf(T key){
		if(key != null){
			for(int i = 0; i < this.length; i ++){
				if(key.equals(elements[i])){// 防止出现空指针异常
					return i;
				}
			}
		}
		return -1;// 空表或则无此对象	
	}

	public T search(T key){// 返回这个元素
		int res = indexOf(key);
		return res == -1 ? null : (T)this.elements[res];
	}

	public boolean contains(T key){
		return indexOf(key) >= 0;
	}
}

测试结果:

查找(一)-----顺序表的顺序查找和折半查找

折半查找:

顺序表的查找是直接遍历, 复杂度是随着这个元素的位置呈线性关系的。所以针对那些已经排好序的顺序表,可以使用折半查找方式,每次取一般,缩小范围。 类似于二叉搜索树(参考:点击打开链接)。

可以采用递归和非递归的方法:(非递归在方法内部直接使用循环,直到找到这个数输出结果。递归就是不断调用这个函数本身即可)。

参考代码:

public class BSArray {

	public static void main(String[] args) {
		int [] arrays = {1, 3, 4, 6, 7, 9 , 11};
		System.out.println(binarySearch(arrays, 0, arrays.length - 1, 6));
		System.out.println(binarySearchRecur(arrays, 0, arrays.length - 1, 7));
	}
	
	//非递归
	public static int binarySearch(int a[], int low, int high, int key){
		int l = low, h = high, midst;
		while(l <= h){
			midst = (l + h) / 2;
			if(key == a[midst]){
				return midst;
			}
			else if(a[midst] > key){
				h = midst - 1;
			}
			else{
				l = midst + 1;
			}
		}
		return -1;
	}
	
	// 递归
	public static int binarySearchRecur(int a[], int low, int high, int key){
		
		if(low > high) {
			return -1;
		}
		else{
            int	midst = (low + high) / 2;
 			if(key == a[midst]){
				return midst;
			}
			else if(a[midst] > key){
				return binarySearchRecur(a, low, midst - 1, key);
			}
			else{
				return binarySearchRecur(a, midst + 1, high, key);
			}
		}
	}
}

测试结果:

查找(一)-----顺序表的顺序查找和折半查找



以上就是这篇的内容。欢迎提出疑问或者错误所在,谢谢!