算法之搜索(Java版)-持续更新补充
一、顺序查找
顺序查找对序列本身没有要求(比如不需要是已经排序好的),也不仅限于数字、字符,也可以用于前缀,对象信息的关键信息的匹配(比如查找指定id的相应信息)。
衡量查找性能的一个指标是————ASL(Average Search Length),ASL=Pi乘Ci,Pi是查找第i个元素的概率,Ci是找到第i个已经比较过次数。
哨兵方式的顺序查找相比较基础的顺序查找在循环的比较部分减少了一般。
//1. 顺序查找 public class SequentialSearch { private int[] array; public SequentialSearch(int[] array) { this.array = array; } public int search(int key) { for(int i = 0; i < array.length; i++) { if(array[i] == key) { return i; } } return -1; } }
//2. 哨兵方式顺序查找 public class Search2 { private int[] array; public Search2(int[] array) { this.array = array; } public int search(int key) { if(key == array[0]) { return 0; } int temp = array[0]; array[0] = key; int index = array.length-1; while(array[index] != key) { index--; } array[0] = temp; if(index == 0) { return -1; }else { return index; } } }
二、二分查找
如果是顺序查找,7个数最多可能会比较7次,但用二分查找,最多只要3次就能OK。时间复杂度是O(logn)(底数为2)。
二分查找的优化————插值查找
如果数据范围是1~100000,让你找10,那么就不一定要从中间找起了。可以三分之一,四分之一处查找,比如1~10,待查为3,那可以从前面三分之一为划分点。对于要查找的位置有个精确的计算公式P=low+(key-a[low])/(a[high]-a[low])*(high-low)
//1. 二分查找递归与非递归的实现 public class BinarySearch { private int[] array; public BinarySearch(int[] array) { this.array = array; } public int searchRecursion(int target) { if(array == null) { return -1; } return searchRecursion(target, 0, array.length - 1); } public int search(int target) { if(array == null) { return -1; } int start = 0; int end = array.length - 1; while(start <= end) { int mid = start + (end - start) / 2; if(array[mid] == target) { return mid; }else if(target < array[mid]) { end = mid - 1; }else { start = mid + 1; } } return -1; } private int searchRecursion(int target, int start, int end) { if(start > end) { return -1; } int mid = start + (end - start) / 2; if(array[mid] == target) { return mid; }else if(array[mid] < target) { return searchRecursion(target, mid + 1, end); }else { return searchRecursion(target, start, mid -1); } } }
//2. 二分插入排序 public class BinaryInsertSort { private int[] array; public BinaryInsertSort(int[] array) { this.array = array; } public void sort() { int length = array.length; for(int i = 1; i < length; i++) { int temp = array[i]; int insertIndex = binarySearch(i - 1, temp); if(insertIndex != i) { for(int j = i; j > insertIndex; j--) { array[j] = array[j - 1]; } array[insertIndex] = temp; } } } public void print() { for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } } private int binarySearch(int end, int target) { int start = 0; int mid = -1; while(start <= end) { mid = start + (end - start) / 2; if(array[mid] > target) { end = mid - 1; }else { //如果相等,也插入到后面 start = mid + 1; } } return start; } }
三、杨氏矩阵的的查找
杨氏矩阵就是行列递增的矩阵。
杨氏矩阵的操作
- 插入。插入一个数,需要移动其他元素
- 删除。给定x,y坐标,删除那个数,伴随其他元素移动,怎样移动操作最少?
- 查找t是否存在于矩阵中。这也是这篇博客里所要关注的。
- 返回第k大的数。涉及到堆查找,后续博客再细说。
关于查找t是否存在于矩阵,书中给了几种实现的方法:
- 递归实现和非递归实现
优化: - 每次不都从每行的第一个数开始查找,左右上下进行比较然后查找。
- 分治法。杨氏矩阵行列是递增的,那么对角线也是递增的,可以利用对角线划分的区域来缩小要查找数的范围。(实现略)
- 定位查找法。先定位到第一行最右的数,然后只需要往下走,往左走两种操作即可,相比方法2省掉了往右走。
public class YoungSearch { private int[][] array; public YoungSearch(int[][] array) { this.array = array; } //1.递归实现 public boolean recursionSearch(int x, int y, int target) { if(x == array.length || y == array[0].length) { return false; } if(target < array[x][y]) { return false; } if(target == array[x][y]) { System.out.println(String.format("x: %d, y: %d", x, y)); return true; } return recursionSearch(x + 1, y, target) || recursionSearch(x, y + 1, target); } //非递归实现 public boolean search(int target) { for(int i = 0; i < array.length; i++) { for(int j = 0; j < array[0].length && target >= array[i][j]; j++) { if(target == array[i][j]) { System.out.println(String.format("x: %d y: %d", i, j)); return true; } } } return false; } //2.简单优化(向左/右/下走) public boolean search2(int target) { int width = array[0].length; int height = array.length; if(target >= array[0][0]) { int i = 0; for(; i < width && target >= array[0][i]; i++) { if(target == array[0][i]) { System.out.println(String.format("x: %d, y: %d", 0, i)); return true; } } if(i > width - 1) { i--; } //循环向下查找 for(int j = 1; j < height; j++) { if(target == array[j][i]) { System.out.println(String.format("x: %d, y: %d", j, i)); return true; }else if(target < array[j][i]) { for(; i >= 0; i--) { if(target == array[j][i]) { System.out.println(String.format("x: %d, y: %d", j, i)); return true; }else if(target > array[j][i]) { break; } } if(i < 0) { i++; } }else if(target > array[j][i]) { for(; i < width; i++) { if(target == array[j][i]){ System.out.println(String.format("x: %d, y: %d", j, i)); return true; }else if(target < array[j][i]) { break; } } if(i > width - 1) { i--; } } } } return false; } //3.进一步优化(从第一行最右边的数开始,只需要向下和向左两个操作) public boolean search3(int target) { int i = 0; int j = array[0].length - 1; int temp = array[i][j]; while(true) { if(target == temp) { System.out.println(String.format("x: %d, y: %d", i, j)); return true; }else if(j > 0 && target < temp){ temp = array[i][--j]; }else if(i < array.length - 1 && target > temp) { temp = array[++i][j]; }else { return false; } } } }
四、分块查找
对于待查找的数据列表来说,如果元素变动很少,那么可以先进行排序再查找。但如果这个数据经常需要添加元素,那么每次查找前都需要排序,这并不是一个好的选择。
就有了分块查找,这个概念再学数据库的时候听过。分块查找里有索引表和分块这两个概念。索引表就是帮助分块查找的一个分块依据,就是一个数组,用来存储每块最大的存储值(范围上限);分块就是通过索引表把数据分为几块。
原理:当需要增加一个元素的时候,先根据索引表,获取这个元素应该在那一块,然后直接把元素加入到相应的块里,而块内的元素直接不需要有序。
从上面可知,分块查找只需要索引表有序,每一个块里的元素可以是无序的,但第i块的每个元素一定比第i-1块的每一个元素大(小)。当索引表很大的时候,可以对索引表进行二分查找,锁定块的位置,然后对块内的元素进行顺序查找。总性能不如二分查找,但强过顺序查找,更好的是不需要数列完全有序。
举个例子,比如索引表为【10,20,30】,分块一【2,1,4,2】分块二【19,15,18,】分块三【22,27,23】,现在要增加22这个数,直接根据索引表把22放到分块三最后就行了【22,27,23,22】。
可以看出,分块查找同时有顺序查找和二分查找的有点————不需要有序、速度快。
应用场景
视频网站对用户观看行为记录,每个用户分别观看了一个视频多久,如果对每条这样的记录都放到一个表里,那太多了,可以根据具体业务做分表,一天一个表,表名如t_user_watch_xxx_20180806
,存储查询的时候就可以根据时间去做一个表的分块,在查询详细的记录。
//分块查找 import java.util.ArrayList; public class BlockSearch { private int[] index; private ArrayList<ArrayList<Integer>> list; public BlockSearch(int[] index) { this.index = index; list = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < index.length; i++) { list.add(new ArrayList<Integer>()); } } public void insert(Integer value) { int i = binarySearch(value); list.get(i).add(value); } public boolean search(int data) { int i = binarySearch(data); for(int j = 0; j < list.get(i).size(); j++) { if(data == list.get(i).get(j)) { return true; } } return false; } public void printAll() { for(int i = 0; i < list.size(); i++) { ArrayList<Integer> l = list.get(i); System.out.println("ArrayList: " + i + ":"); for(int j = 0; j < l.size(); j++) { System.out.println(l.get(j)); } } } private int binarySearch(int target) { int start = 0; int end = index.length - 1 ; int mid = -1; while(start <= end) { mid = (start + end) / 2; if(target == index[mid]) { return mid; }else if(target < index[mid]) { end = mid - 1; }else { start = mid + 1; } } return start; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
程序员都秃顶?Python创始人笑了,养生还得学这门语言
程序员爱脱发,是不争的事实,经常面对电脑,工作压力大,都会导致脱发的产生。正所谓“聪明绝顶”,越厉害的程序员,谢顶的可能性就越大。那么,我们看看世界上顶级的程序员们,看看是否能从中找到规律。 这位大牛,很多人都认识,C语言之父——丹尼斯·里奇。里奇的C语言,养活了世界上成千上万的程序员,可能是对人类做出的贡献太大了,2011年,在乔布斯去世一个礼拜后,上帝带走了他。 里奇的脱发等级在2级到3级之间,发际线比较高,额头也比较大,但头顶部位还是比较浓密的。C语言算不上特别难,看来齐大爷保养的也是非常的棒。 多少程序员要感谢里奇赏了你们饭碗了。 在TIOBE编程语言排行榜上,有这么一门语言,霸占排行榜榜首多年,这门计算机语言,就是Java,詹姆斯·高斯林在1990和他人一起创造了Java,因此他被称为Java之父。 高斯林的脱发等级已经达到了6级,前额部位基本脱落,头顶部位向后扩散,中间仅剩下隔离狭窄的毛发带了。不得不说高斯林是劳心劳力的,Java多么伟大的语言,想要搞定它,还真得多费工夫。 作为Java的兄弟语言,C++同样非常热门,开发游戏、科学计算、网络软件、分布式应用等等,都离不开C...
- 下一篇
一线互联网公司Java高级面试题总结
Java重点知识 多线程(线程状态、线程并发,Synchronized与Lock的区别和底层原理,常用的锁及其使用场景和原理,volatile和ThreadLocal解决了什么问题,CAS在Java中的实现线程池原理和实现,阻塞队列和线程安全队列,线程间通信: synchronized + wait、notify/notifyAll, Lock + Condition 的多路复用,CountDownLatch、CyclicBarrier和Semaphore的作用和用法,使用场景)JVM内存管理机制和垃圾回收机制(内存模型、GC策略、算法、分代回收GC类型,Full GC、Minor GC作用范围和触发条件)JVM内存调优(内存调整的6个参数,了解是怎么回事,一般做项目过程中使用较多)设计模式(熟悉常见设计模式的应用场景,会画类图,常用:代理,2个工厂,策略,单例,观察者,适配器,组合与装饰)JAVA集合类框架(理解框架图、HashMap、ArrayList、HashSet等的关系和区别,其中HashMap的存储机制几乎每次都有问)HashMap的原理,底层数据结构,rehash的过程,...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8安装Docker,最新的服务器搭配容器使用
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS7设置SWAP分区,小内存服务器的救世主
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8编译安装MySQL8.0.19
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS关闭SELinux安全模块
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题