文档章节

查找算法总结

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 664
阅读 0
收藏 0
点赞 0
评论 0

1、顺序查找

  条件:无序或有序队列。
  原理:按顺序比较每个元素,直到找到关键字为止。
  时间复杂度:O(n)
  

代码:

public static int SequenceSearch(int[] sz, int key) {

        for (int i = 0; i < sz.length; i++) {

            if (sz[i] == key) {

                return i;

            }

        }

        return -1;

    }

2、二分查找(折半查找)

  条件:有序数组
  原理:查找过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;
     如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
     如果在某一步骤数组为空,则代表找不到。
     这种搜索算法每一次比较都使搜索范围缩小一半。
  时间复杂度:O(logn)

代码:

我之前的关于二分查找的博客

3.、二叉排序树查找

  条件:先创建二叉排序树:
      1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
      2. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
      3. 它的左、右子树也分别为二叉排序树。
  原理:
    在二叉查找树b中查找x的过程为:
    1. 若b是空树,则搜索失败,否则:
    2. 若x等于b的根节点的数据域之值,则查找成功;否则:
    3. 若x小于b的根节点的数据域之值,则搜索左子树;否则:
    4. 查找右子树。
  时间复杂度:O(\log_2(n))  

4、哈希表法(散列表)

  条件:先创建哈希表(散列表)
  原理:根据键值方式(Key value)进行查找,通过散列函数,定位数据元素。
  时间复杂度:几乎是O(1),取决于产生冲突的多少。

5、分块查找

  原理:将n个数据元素”按块有序”划分为m块(m ≤ n)。
     每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;
     而第2块中任一元素又都必须小于第3块中的任一元素
     
参考:
http://www.cnblogs.com/butyoux/archive/2013/01/15/2861291.html
http://krelve.com/m/?post=82

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆 ⋅ 2011/12/03 ⋅ 0

二分查找算法

今天在公司闲着蛋疼,网上瞎逛,偶然在InfoQ网站上看到一篇文章《计算机科学中最重要的32个算法》,原文地址:http://www.infoq.com/cn/news/2012/08/32-most-important-algorithms?utmsour...

JackieYeah ⋅ 2013/07/09 ⋅ 0

Python数据结构总结篇

数据结构篇主要是阅读[Problem Solving with Python](http://interactivepython.org/courselib/static/pythonds/index.html)时写下的阅读记录,当然,也结合了部分[算法导论](http://en.wik...

宅男潇涧 ⋅ 2014/07/06 ⋅ 0

查找算法总结

查找算法:顺序查找、二分查找、分块查找、二叉查找树、B树、B+树 一、二分查找(常规) 题目描述: (牛客网http://www.nowcoder.com/practice/28d5a9b7fc0b4a078c9a6d59830fb9b9?rp=1&ru=/...

阿阿阿阿阿局 ⋅ 2016/07/28 ⋅ 0

为什么 GNU grep 如此之快?

编注:这是GNU grep的原作者Mike Haertel 在FreeBSD邮件列表中对 “GNU grep为什么比BSD grep要快” 所做的回答,下面是邮件正文内容: Gabor 您好, 我是GNU grep的原作者,同时也是一名Fre...

oschina ⋅ 2013/12/05 ⋅ 31

snort 中的Boyer-Moore

声明 snort中的字串查找,以下代码出自snort-2.9.6.0。是snort中用于字串匹配的底层接口。主要是参考了Boyer-Moore算法进行实现的. 关于Boyer-Moore的文章可以参考: http://my.oschina.net/u...

面码 ⋅ 2014/07/09 ⋅ 0

Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛 ⋅ 2017/11/10 ⋅ 0

常见算法的记录

快速排序 时间复杂度 O(n*log2n) 总结起来,快排的核心算法只有两步: 1)sort排序函数中,调用分区函数partition,将大的数组分成两块,然后再分别调用sort函数,这是一个递归过程。 2)par...

文森特梵高 ⋅ 2015/08/20 ⋅ 0

各种经典算法总结

二分排序 / 二分查找 算法思想:1、将数组排序(从小到大);2、每次跟中间的数mid比较,如果相等可以直接返回, 如果比mid大则继续查找大的一边,否则继续查找小的一边。 输入:排序好的数组 ...

长平狐 ⋅ 2013/01/06 ⋅ 0

zg手册 之 python2.7.7源码分析(3)-- list 对象和 dict 对象

list 对象 list 对象的定义 list对象内部是使用数组实现,在数组中存储的是指针,指向要保存的对象。 allocated是list中数组的大小,ob_size是当前已经使用的数组大小。 typedef struct { /...

东昕 ⋅ 2014/08/26 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Python模块/包/库安装(6种方法)

Python模块/包/库安装(6种方法) 冰颖机器人 2016-11-29 21:33:26 一、方法1: 单文件模块 直接把文件拷贝到 $python_dir/Lib 二、方法2: 多文件模块,带setup.py 下载模块包(压缩文件zip...

cswangyx ⋅ 13分钟前 ⋅ 0

零基础学习大数据人工智能,学习路线篇!系统规划大数据之路?

大数据处理技术怎么学习呢?首先我们要学习Python语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 Python:Python 的排名从去年开始就借助人工智能持续上升,现在它已经...

董黎明 ⋅ 22分钟前 ⋅ 0

openJdk和sun jdk的区别

使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的OpenJDK, 那么到底什么是OpenJDK,它与SUN JDK有什么关系和区别呢? 历史上的原因是,Ope...

jason_kiss ⋅ 31分钟前 ⋅ 0

梳理

Redux 是 JavaScript 状态容器,提供可预测化的状态管理。 它是JS的状态容器,是一种解决问题的方式,所以即可以用于 react 也可以用于 vue。 需要理解其思想及实现方式。 应用中所有的 stat...

分秒 ⋅ 44分钟前 ⋅ 0

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 今天 ⋅ 0

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 今天 ⋅ 0

到底会改名吗?微软GVFS 改名之争

微软去年透露了 Git Virtual File System(GVFS)项目,GVFS 是 Git 版本控制系统的一个开源插件,允许 Git 处理 TB 规模的代码库,比如 270 GB 的 Windows 代码库。该项目公布之初就引发了争...

linux-tao ⋅ 今天 ⋅ 0

笔试题之Java基础部分【简】【二】

1.静态变量和实例变量的区别 在语法定义上的区别:静态变量前要加static关键字,而实例变量前则不加。在程序运行时的区别:实例变量属于某个对象的属性,必须创建了实例对象,其中的实例变...

anlve ⋅ 今天 ⋅ 0

Lombok简单介绍及使用

官网 通过简单注解来精简代码达到消除冗长代码的目的 优点 提高编程效率 使代码更简洁 消除冗长代码 避免修改字段名字时忘记修改方法名 4.idea中安装lombnok pom.xml引入 <dependency> <grou...

to_ln ⋅ 今天 ⋅ 0

【转】JS浮点数运算Bug的解决办法

37.5*5.5=206.08 (JS算出来是这样的一个结果,我四舍五入取两位小数) 我先怀疑是四舍五入的问题,就直接用JS算了一个结果为:206.08499999999998 怎么会这样,两个只有一位小数的数字相乘,怎...

NickSoki ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部