查找(一)-----顺序表的顺序查找和折半查找
程序员文章站
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);
}
}
}
}
测试结果:
以上就是这篇的内容。欢迎提出疑问或者错误所在,谢谢!
推荐阅读
-
顺序查找/二分查找/冒泡排序/打印金字塔/打印乘法表
-
有15个数按由大到小顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中 第几个元素的值。如果该数不在数组中,则输出“无此数”。
-
有15个数按由大到小顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则输出“无此数”——C语言
-
有15个数按从小到大顺序存放在一个数组中,输入一个数,输出一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则输出“无此数”。
-
PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解_PHP
-
PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解_PHP
-
php使用substr()和strpos()联合查找字符串中某一特定字符的方法
-
PHP查找一周内的数据 和一段范围的数据 如何写SQL
-
「力扣」第 34 题:在排序数组中查找元素的第一个和最后一个位置(二分查找)
-
PHP查找一周内的数据 和一段范围的数据 如何写SQL