查找（一）-----顺序表的顺序查找和折半查找

article/2025/10/12 13:48:31

顺序表的顺序查找：

基于顺序表，查找指定的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);}}}
}

测试结果：