1 二分查找/折半查找
思想:在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
时间复杂度:折半搜索每次把搜索区域减少一半,时间复杂度为或log2(n)。(注意log2(n)和log(n)其实是同样的复杂度,因为它们之间仅仅差了一个常量系数而已)。(n代表集合中元素的个数)
空间复杂度:。虽以递归形式定义,但是尾递归,可改写为循环。
适用范围:优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
最多最少:元素有序时折半查找:最多+1次,最少1次;元素无序只能顺序查找:最多n次,最少1次
public class BinarySearch { /** * 二分查找算法,非递归 * * @param srcArray 有序数组 * @param des 查找元素 * @return des的数组下标,没找到返回-1 */ public static int binarySearch(int[] srcArray, int des) { int low = 0; int high = srcArray.length-1; while(low <= high) { int middle = (low + high)/2; if(des == srcArray[middle]) { return middle; } else if(des <srcArray[middle]) { high = middle - 1; } else { low = middle + 1; } } return -1; } public static void main(String[] args) { int[] src = new int[] {1, 3, 5, 7, 8, 9}; System.out.println(binarySearch(src, 3)); } }
//折半查找递归算法 //查询成功返回该对象的下标序号,失败时返回-1。 int BiSearch2(int r[],int low,int high,int k) { if(low>high) return -1; else { int mid=(low+high)/2; if(r[mid]==k) return mid; else if(r[mid]<k) return BiSearch2(r,mid+1,high,k); else return BiSearch2(r,low,mid-1,k); } }
public static void main(String[] args) { int r[]={1,2,3,4,5}; System.out.println(BiSearch2(r,1,5,5)); }
参考:http://zh.wikipedia.org/wiki/%E6%8A%98%E5%8D%8A%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95
http://www.2cto.com/kf/201212/172713.html
2 二叉排序树
又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:
①若它的左子树非空,则左子树上所有结点的值均小于根结点的值;②若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
③左、右子树本身又各是一棵二叉排序树。
相关推荐
《Java常用算法手册》分三篇,共13章,分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述,然后重点分析了数据结构和基本算法思想;接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏...
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序
第5章 查找算法 第6章 基本数学问题 第7章 数据结构问题 第8章 数论问题 第9章 算法经典趣题 **0章 游戏中的算法 **1章 密码学概述 **2章 压缩与解压缩算法 第3篇 算法面试篇 **3章 数学能力测试 **4章 算法面试题
接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏、密码学等领域中的应用:最后,列举了算法的一些常见面试题。书中知识点覆盖全面,结构安排紧凑,讲解详细,实例丰富。全书对每一个知识点都给出了相 ...
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
查找算法 •1 概念 •2 顺序查找 •3 二分查找 •4 分块查找 •5 哈希表查找
Java常用高效8大排序算法与二分法查找,适合正在学习算法和准备学习算法的算法爱好者和研究使用算法的开发人员使用。
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
JavaAlgorithm Java 常用算法学习过程 数据结构 ...查找算法 基本数学问题 数据结构问题 数论问题 算法经典趣题 游戏中的算法 简单的 Java 上机面试问题 逻辑推理面试问题 数学能力测试 算法面试题
在java中,我们常用的查找有四种: 顺序(线性)查找 二分查找/折半查找 插值查找 斐波那契查找 线性查找 思路: 如果在数组中发现满足条件的值, 就返回其下标 /** * 线性查找 * @author TimePause * @create 2020-02...
十种常用算法之二分查找(java版)(csdn)————程序
二分法查找是一种常用的查找算法,也称为折半查找。它适用于有序数组中查找某个元素的位置。二分法查找的思路是将数组分成两部分,每次查找都将待查找区间缩小一半,直到找到目标元素或者待查找区间为空为止。 ...
5.4.1 顺序表结构中的查找算法 145 5.4.2 链表结构中的查找算法 148 5.4.3 树结构中的查找算法 151 5.4.4 图结构中的查找算法 152 5.5 小结 153 第6章 基本数学问题 154 6.1 判断闰年 154 6.2 多项式计算 ...
* 顺序查找 * @param sz * @param key * @return 下标 */ public static int SequenceSearch(int[] sz, int key) { for (int i = 0; i < sz.length; i++) { if (sz[i] == key) { return i; } } return...