notebooks
  • notebooks
  • _planning
    • 2022 OKR
    • basketball
    • swimming
  • communication
    • Dubbo
    • Kafka
    • Messaging
    • RPC
    • Thrift
  • computation
    • map-reduce
  • cs-basic-knowledge
    • computer-architecture
    • data-structure-and-algorithms
    • networks
    • os
  • devops
    • Docker
    • Linux
    • Prometheus
    • operations
    • security
    • trouble-shooting
  • distributed-knowledge
    • Zookeeper_CMD
    • distributed-system
  • game-engine
    • Unity
  • others
    • appium使用
  • protocols
    • http(s)协议
    • 官方链接
    • sip
  • storage
    • Elasticsearch
    • GuavaCache
    • MySQL
    • MySQL_CMD
    • NoSQL
    • Redis
    • Redis_CMD
  • system-design
    • system-design
  • tools
    • Git
    • IDEA
    • Mac
    • VScode
    • Vim
  • _working
    • doc-template
      • backend-design-review
      • correction-of-error
      • service-review
    • process
      • domain-backup
      • oncall
  • blogs
    • history
      • 8088/8086微处理器
      • 8088/8086指令系统
      • CSS-DOM
      • CSS定位
      • CSS工作原理
      • CSS控制背景
      • CSS浮动布局
      • CSS盒模型
      • Chrome开发者工具使用方法
      • DOM
      • Django Model模型层学习
      • Django-REST-framework Serializers学习
      • Django-REST-framework Views和ViewSets学习
      • Django View视图层学习
      • Gvim下Emmet安装及使用教程
      • HTTP协议简介
      • HashMap原理初探
      • JavaScript简史
      • JavaScript语法
      • Java内存模型和GC机制
      • Java基础——Lambda学习
      • Java基础——方法引用
      • Java基础——枚举类型
      • Java类加载机制
      • KMP算法
      • Kafka学习
      • Linux下用命令行编译Java程序
      • MathJax简介和基本用法
      • Python实现常见数据结构
      • Python装饰器总结
      • TCP协议的三次握手和四次挥手
      • Thrift学习
      • asyncio学习
      • markdown的常用语法
      • 修改hosts文件实现翻墙
      • 充实文档的内容
      • 关系数据库
      • 关系数据库标准语言SQL(一)
      • 关系数据库标准语言SQL(二)
      • 关系数据理论
      • 关系查询处理和查询优化
      • 内联元素和块级元素
      • 剑指offer算法题练习
      • 动态创建标记
      • 图形化用户界面
      • 在Eclipse中使用Maven构建Java Web项目
      • 增加微博秀遇到的一些问题
      • 处理机调度
      • 如何用github和hexo搭建个人博客
      • 存储管理
      • 存储系统的层次结构
      • 学习模仿lionhit网站首页的过程总结
      • 实用的GitHub小技巧
      • 并发控制
      • 循环与分支程序设计
      • 指令系统的设计
      • 指令级并行及其开发——硬件方法
      • 搭建自己的VPN服务器
      • 操作系统用户界面
      • 数据库安全性
      • 数据库完整性
      • 数据库恢复技术
      • 数据库绪论
      • 数据库编程
      • 数据库设计
      • 数据抽象
      • 文件系统
      • 文法和语言
      • 最佳实践
      • 案例研究:JavaScript图片库
      • 案例研究:图片库改进版
      • 汇编语言程序格式
      • 汇编语言程序设计基础知识
      • 流水线技术
      • 深度优先搜索和广度优先搜索
      • 牛客网——网易2017秋招编程题集合
      • 用JavaScript实现动画效果
      • 第一篇博客
      • 经典排序算法总结(Java实现)
      • 经典查找算法总结(Java实现)
      • 综合示例
      • 编译原理引论
      • 背包、队列和栈
      • 虚拟机安装Linux系统及常用软件
      • 计算机操作系统绪论
      • 计算机系统结构的基础知识
      • 设备管理
      • 设计模式之代理模式
      • 设计模式之单例模式
      • 设计模式之工厂模式
      • 设计模式之策略模式
      • 设计模式之观察者模式
      • 词法分析
      • 进程管理
      • 闭包
      • 阻止Google自动跳转到香港服务器的方法
      • 项目部署过程
  • programming-language
    • C#
      • C#
    • C&C++
      • C
    • C&C++
      • C++
    • Java
      • GoogleGuice
    • Java
      • JVM
    • Java
      • Java
    • Java
      • Maven
    • Java
      • Mybatis
    • Java
      • Spring知识
    • Java
      • SpringBoot
    • Java
      • Tomcat
    • Python
      • Python
    • Shell
      • Shell
  • wheels
    • dcc
      • 产品调研
      • 方案设计
    • red-envelope
      • 方案设计
    • short-url
      • 短链接服务
    • sso
      • 方案设计
Powered by GitBook
On this page
  • 顺序查找
  • 说明
  • 基本思想
  • 实现源码
  • 二分查找
  • 说明
  • 基本思想
  • 实现源码
  • 插值查找
  • 说明
  • 基本思想
  • 实现源码
  • 斐波那契查找
  • 说明
  • 基本思想
  • 实现源码
  • 二叉查找树
  • 说明
  • 基本思想
  • 实现源码
  • 总结
  1. blogs
  2. history

经典查找算法总结(Java实现)

经典查找算法主要有顺序查找、二分查找、插值查找、斐波那契查找、二叉查找树等,这里用Java语言实现这些算法。

顺序查找

说明

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想

顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。

实现源码

public int sequenceSearch(int[] arr, int key){
	for(int i=0;i<arr.length;i++){
		if(arr[i]==key){
			return i;
		}
	}
	return -1;
}

二分查找

说明

元素必须是有序的,如果是无序的则要先进行排序操作。

基本思想

也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。

实现源码

//循环
public int binarySearch(int[] arr, int key){
	int low=0, high=arr.length-1;
	while(low<=high){
		int mid=(low+high)/2;
		if(arr[mid]==key){
			return mid;
		}
		if(arr[mid]<key){
			low=mid+1;
		}
		if(arr[mid]>key){
			high=mid-1;
		}
	}
	return -1;
}
	
//递归
public int binarySearch1(int[] arr, int key, int low, int high){
	if(low>high){
		return -1;
	}

	int mid=(low+high)/2;
	if(arr[mid]==key){
		return mid;
	}
	if(arr[mid]<key){
		return binarySearch1(arr, key, mid+1, high);
	} else {
		return binarySearch1(arr, key, low, mid-1);
	}
}

插值查找

说明

在英文字典里面查“apple”,你下意识翻开字典是翻前面的书页还是后面的书页呢?如果再让你查“zoo”,你又怎么查?很显然,这里你绝对不会是从中间开始查起,而是有一定目的的往前或往后翻。同样的,比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5, 我们自然会考虑从数组下标较小的开始查找。 二分查找这种查找方式,不是自适应的。二分查找中查找点计算如下:mid=(low+high)/2, 即mid=low+1/2*(high-low)。我们可以将查找的点改进为如下:mid=low+(key-a[low])/(a[high]-a[low])*(high-low),也就是将上述的比例参数1/2改进为自适应的,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。 对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。

基本思想

基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。

实现源码

//循环
public int insertSearch(int[] arr, int key){
	int low=0, high=arr.length-1;
	while(low<=high){
		int mid=low+(key-arr[low])/(arr[high]-arr[low])*(high-low);
		if(arr[mid]==key){
			return mid;
		}
		if(arr[mid]<key){
			low=mid+1;
		}
		if(arr[mid]>key){
			high=mid-1;
		}
	}
	return -1;
}
	
//递归
public int insertSearch1(int[] arr, int key, int low, int high){
	if(low>high){
			return -1;
	}
		
	int mid=low+(key-arr[low])/(arr[high]-arr[low])*(high-low);
	if(arr[mid]==key){
		return mid;
	}
	if(arr[mid]<key){
		return insertSearch1(arr, key, mid+1, high);
	}else {
		return insertSearch1(arr, key, low, mid-1);
	}
}

斐波那契查找

说明

基本思想

斐波那契查找是根据斐波那契序列的特点对表进行分割。假设表中记录的个数比某个斐波那契数小1,即n=Fn−1,然后将给定值和表中第Fn−1个记录的关键字进行比较。若相等,则查找成功;若给定关键字<表中第Fn−1个记录的关键字,则继续在表中从第一个记录到第Fn−1−1个记录之间查找;若给定关键字>表中第Fn−1个记录的关键字,则继续在自Fn−1+1至Fn−1的子表中查找。

实现源码

//斐波那契数列长度,按使用场景变化
public static final int MAX_SIZE=30;
	
public int fibonacciSearch(int[] arr, int key){
	int len=arr.length;

/*1.构造斐波那契数组
	//构造斐波那契数组
	int[] fib=fibnacci(MAX_SIZE);
	//len位于斐波那契数列的位置
	int k=0;
	while(len>(fib[k]-1)){
		k++;
	}
	//将数组arr扩展到fib[k]-1的长度
	int[] temp=new int[fib[k]-1];
	for(int i=0;i<len;i++){
		temp[i]=arr[i];
	}
	//保持temp数组仍然有序
	for(int i=len;i<fib[k]-1;i++){
		temp[i]=arr[len-1];
	}
*/
		
//2.获取所需斐波那契数
	//确定需要的斐波那契数
	int k=0;
	while(len>getFibnacci(k)-1){
		k++;
	}
	//将数组arr扩展到fib[k]-1的长度
	int[] temp=new int[getFibnacci(k)-1];
	for(int i=0;i<len;i++){
		temp[i]=arr[i];
	}
	//保持temp数组仍然有序
	for(int i=len;i<getFibnacci(k)-1;i++){
		temp[i]=arr[len-1];
	}

	int low=0, high=temp.length-1;
	while(low<=high){
		int mid=low+getFibnacci(k-1);
		if(temp[mid]==key){
			//判断是否是扩展的数值
			if(mid<len){
				return mid;	
			}else {
				return len-1;
			}
		}else
		if(temp[mid]<key){
			low=mid+1;
			k=k-1;
		}else {
			high=mid-1;
			k=k-2;
		}
	}
	return -1;
}
	
//得到第n个斐波那契数
public int getFibnacci(int n){
	int result=0;
	int fib0=0, fib1=1;
	if(n==0){
		return fib0;
	}
	if(n==1){
		return fib1;
	}
	for(int i=2;i<=n;i++){
		result=fib0+fib1;
		fib0=fib1;
		fib1=result;
	}
	return result;
}
	
//构造斐波那契数列
public int[] fibnacci(int n){
	int[] result=new int[n];
	result[0]=0;
	result[1]=1;
	for(int i=2;i<n;i++){
		result[i]=result[i-1]+result[i-2];
	}
	return result;
}

二叉查找树

说明

二叉查找树(又称二叉排序树、二叉搜索树)或者是空树,或者是具有下列性质的一颗树:

  • 若他的左子树不为空,则左子树上所有结点的值均小于其根节点的值;

  • 若他的右子树不为空,则右子树上所有结点的值均大于其根节点的值;

  • 他的左右子树也均是二叉排序树。

二叉查找树性质:对二叉查找树进行中序遍历,即可得到有序的数列。

基本思想

二叉查找树是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。 这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。

实现源码

public class BSTSearch {
	// 递归
	public boolean bstSearch(BSTreeNode root, int key) {
		if (root.data == key) {
			return true;
		} else if (root.data < key) {
			return bstSearch(root.right, key);
		} else {
			return bstSearch(root.left, key);
		}
	}

	// 循环
	public boolean bstSearch1(BSTreeNode root, int key) {
		BSTreeNode node = root;
		while (node != null) {
			if (node.data == key) {
				return true;
			}
			if (node.data < key) {
				node = node.right;
			}
			if (node.data > key) {
				node = node.left;
			}
		}
		return false;
	}
}

class BSTreeNode {
	public int data;
	public BSTreeNode left;
	public BSTreeNode right;

	public BSTreeNode(int data) {
		this.data = data;
	}

	public BSTreeNode(int data, BSTreeNode left, BSTreeNode right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}
}

总结

复杂度比较:

类别
时间复杂度

顺序查找

O(n)

二分查找

O($\log_2{n}$)

插值查找

O($\log_2(\log_2{n})$)

斐波那契查找

O($\log_2{n}$)

二叉查找树

O($\log_2{n}$) ~ O(n)


Previous经典排序算法总结(Java实现)Next综合示例

Last updated 3 years ago

经典查找算法总结(Java实现)1

[Data Structure & Algorithm] 七大查找算法
常见查找算法(Java实现)