查找简单理解即为在集合中查询获取需要的元素,不同的查询条件以及集合中数据的存储方式决定了使用不同的查找方法。
查找的分类
静态查找:只查找,不改变集合内的数据元素,例如:顺序查找,二分查找,分块查找
动态查找:既查找,又改变集合(增删)内的数据元素,例如:二叉树查找
1、顺序查找
又称线性查找,是从数组的第一个元素开始查找,直到找到待查找元素的位置,直到查找到结果。 最佳的状况时间是1 ,就是第一个就是待查找的远射,最差的查找状况是O(n),就是最后一个是待查找的元素。
算法思路:给定一个key值,在数组中顺序对比,若存在k = key,则查找成功,返回数组中该元素下标,失败返回-1;
int order(int[] array, int tar) {
for (int i = 0; i < array.length; i++) {
if (tar == array[i])
return i + 1;
}
return -1;
}
2、二分查找
又称折半查找,是将待查找的数组元素不断的分为两部分,每次淘汰二分之一,但是有个大前提是,元素必须是有序的,如果是无序的则要先进行排序操作,这种查找的方法,类似于找英文字典的Java,我们可以一下子找到字母J开头的,再仔细找。 最佳的状况时间是1,就是第一次分开就查找到了,最差的查找状态是O(n),便是待查找的数据出现在最后一次。
前提:元素必须是有序的,如果是无序的则要先进行排序操作
二分法查找递归实现
public class testBinaryOne {
public static Integer testBinarySearch(int[] a,int key,int low,int high){
if(low > high){
return -1;
}
while(low <= high){
int mid = (low + high)/2;
if(key == a[mid]){
return mid;
}else if(key < a[mid]){
return testBinarySearch(a,key,low,mid-1);
}else{
return testBinarySearch(a,key,mid+1,high);
}
}
return -1;
}
public static void main(String[] args){
int[] a = {1,3,5,7,9,11,13,16,22,55};
Integer mm = testBinarySearch(a, 16,0,a.length);
System.out.println("16的位置在:"+ mm +"位");
}
}
二分法查找非递归实现
public class TestSearch {
public static Integer testBinarySearch(int[] a,int key){
int low = 0;
int high = a.length;
if(low > high){
return -1;
}
while(low <= high){
int mid = (low + high)/2;
if(key == a[mid]){
return mid;
}else if(key < a[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}
return -1;
}
public static void main(String[] args){
int[] a = {1,3,5,7,9,11,13,16,22,55};
Integer mm = testBinarySearch(a, 16);
System.out.println("16的位置在:"+ mm +"位");
}
}
3、分块查找
分块查找又称索引顺序查找,它是顺序查找的一种改进方法。
一、先选取各块中的最大关键字构成一个索引表;
二、查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;
然后,在已确定的块中用顺序法进行查找。
typedef int keytype;
typedef struct {
keytype Key;
}elemtype;
typedef struct{
keytype Key;
int Link;
}indextype;
/**
* 分块查找关键字为Key的记录。索引表为ls[0]-ls[m-1],顺序表为s,块长为l
*/
int IndexSequelSearch(indextype ls[],elemtypes[],int m,int l,keytype Key){
int i,j;
/*在索引表中顺序查找*/
i=0;
while(i<m&&Key>ls[i].Key)i++;
if(i>=m)
return -1;
else{
/*在顺序表中顺序查找*/
j=ls[i].Links;
while(Key!=s[j].Key&&j-ls[i].Link<l)
j++;
if(Key==s[j].Key)
return j;
else
return -1;
}
}
4、二叉树查找
二叉查找树是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。
这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。
// 二叉树递归查找算法
BinaryTreeNode binaryTreeRecusion(BinaryTreeNode bt, Object tar) {
if (bt == null)
return new BinaryTreeNode("null");
switch (strategy.compare(tar, bt.getData())) {
case -1:// tar比data小就查找左子树
return binaryTreeRecusion(bt.getLeftChild(), tar);
case 1:// tar比data大就查找右子树
return binaryTreeRecusion(bt.getRightChild(), tar);
default:// 比较结果是0,tar和data相等就返回
return bt;
}
}
// 二叉树非递归查找算法
BinaryTreeNode binaryTree(BinaryTreeNode bt, Object tar) {
while (bt != null) {
switch (strategy.compare(tar, bt.getData())) {
case -1:// tar比data小就查找左子树
return bt = bt.getLeftChild();
case 1:// tar比data大就查找右子树
return bt = bt.getRightChild();
default:// 比较结果是0,tar和data相等就返回
return bt;
}
}
return new BinaryTreeNode("null");
}
分享到:
相关推荐
几种常用查找算法的比较,内含顺序查找、二分查找、二叉树查找、哈希表查找。
常用查找详细算法 包括顺序查找,二分查找,分块查找,二叉排序树查找,哈希查找
3种查找算法,顺序查找 折半查找 索引查找,c语言编写,可直接运行
查找算法 •1 概念 •2 顺序查找 •3 二分查找 •4 分块查找 •5 哈希表查找
常用查找算法[定义].pdf
常用排序和查找算法的源程序,包括冒泡排序,选择排序,插入排序,折半查找,c++实现
P246~250C++常用查找算法学习笔记.docx
常用排序查找算法详解:各种排序查找算法
在该程序中,实现了数据结构中比较常见的一些查找算法,那么希望能够对朋友你有用。
根据自己搜集的资料很实际实用,总结了几种常用的查找算法
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契...
区间表(表中每一元素表示的是一个范围的数据)的查找是一个常见的问题,在表的长度较小或要查找元素的数量不多的情况下,折半查找是一种不错并且容易实现的算法。但在某些特殊的行业(如电信业)由于要对长度较大的...
排序包括希尔、冒泡、快排、选择排序、堆排序、归并排序,查找包括顺序、折半、二叉排序树(包括关键字添加删除)、B树.
几种简单常用的查找算法,饱含binsearch,bstree,Hash,seqsearch。
主要包含冒泡 插入 选择 希尔 快速排序 堆排序 折半查找等常用的数据结构排序算法的实现
算法 常用算法 排序 查找 零基础学算法源码 NOIP普及组试题精解 NOIP提高组试题精解
常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符串匹配算法:字符串匹配算法用于在一个字符串(文本)中查找一个子串(模式)的出现位置。常见的字符串匹配算法包括暴力匹配、KMP算法、Boyer...
查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。
各种查找算法。常用算法集(C语言描述)。
《Java常用算法手册》分三篇,共13章,分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述,然后重点分析了数据结构和基本算法思想;接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏...