1、前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序
2、原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚,若是不理解可以去网上找。从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现。所以我们的实现分为递归和循环两种,可以根据代码来理解算法
3、实现:代码如下
-
packageorg.cyxl.algorithm.search;
-
-
-
-
-
-
-
publicclassBinarySearch{
-
privateintrCount=0;
-
privateintlCount=0;
-
-
-
-
-
-
publicintgetrCount(){
-
returnrCount;
-
}
-
-
-
-
-
-
publicintgetlCount(){
-
returnlCount;
-
}
-
-
-
-
-
-
-
-
-
-
publicintsearchRecursive(int[]sortedData,intstart,intend,intfindValue)
-
{
-
rCount++;
-
if(start<=end)
-
{
-
-
intmiddle=(start+end)>>1;
-
-
intmiddleValue=sortedData[middle];
-
-
if(findValue==middleValue)
-
{
-
-
returnmiddle;
-
}
-
elseif(findValue<middleValue)
-
{
-
-
returnsearchRecursive(sortedData,start,middle-1,findValue);
-
}
-
else
-
{
-
-
returnsearchRecursive(sortedData,middle+1,end,findValue);
-
}
-
}
-
else
-
{
-
-
return-1;
-
}
-
}
-
-
-
-
-
-
-
-
publicintsearchLoop(int[]sortedData,intfindValue)
-
{
-
intstart=0;
-
intend=sortedData.length-1;
-
-
while(start<=end)
-
{
-
lCount++;
-
-
intmiddle=(start+end)>>1;
-
-
intmiddleValue=sortedData[middle];
-
-
if(findValue==middleValue)
-
{
-
-
returnmiddle;
-
}
-
elseif(findValue<middleValue)
-
{
-
-
end=middle-1;
-
}
-
else
-
{
-
-
start=middle+1;
-
}
-
}
-
-
return-1;
-
}
-
}
4、测试代码
-
packageorg.cyxl.algorithm.search.test;
-
-
importorg.cyxl.algorithm.search.BinarySearch;
-
importorg.junit.Test;
-
-
-
publicclassBinarySearchTest{
-
@Test
-
publicvoidtestSearch()
-
{
-
BinarySearchbs=newBinarySearch();
-
-
int[]sortedData={1,2,3,4,5,6,6,7,8,8,9,10};
-
intfindValue=9;
-
intlength=sortedData.length;
-
-
intpos=bs.searchRecursive(sortedData,0,length-1,findValue);
-
System.out.println("Recursice:"+findValue+"foundinpos"+pos+";count:"+bs.getrCount());
-
intpos2=bs.searchLoop(sortedData,findValue);
-
-
System.out.println("Loop:"+findValue+"foundinpos"+pos+";count:"+bs.getlCount());
-
}
-
}
5、总结:这种查找方式的使用场合为已排序的数组。可以发现递归和循环的次数是一样的
分享到:
相关推荐
算法-数据结构和算法-15-二分查找.rar
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
《数据结构与算法》-李春葆 实验报告-典型查找算法实践-二分查找、分块索引查找
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
Java数据结构和算法中文第二版(1) Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
常见的算法包括排序算法(如冒泡排序、快速排序)、搜索算法(如二分查找)、图算法(如最短路径算法)等。掌握这些算法的思想和实现方式,可以提高代码的效率和性能。此外,算法设计中的一些基本思想,如递归、动态规划、...
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
数据结构八大算法,详细介绍了算法的如何实现,以及编码过程,有简单到复杂,由浅入深,看看会有很大收获。
01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示与实现、线性表的基本操作 02-003单链表的创建与操作、加工型...
数据结构-查找算法 二分查找 二叉顺序数 哈希查找
数据结构 查找 源代码 二分查找的算法源码,两种算法的效率比较
讲述了数据结构中的几种查找算法,比如二分查找算法等,分析了其平均长度,时间以及空间开销
(1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 (3) 设计算法在...
通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择正确的算法 利用数据结构和算法为现实世界的处理过程建模 了解不同的数据结构的优势和弱点,考虑如何利用...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? ...
指某些著名的数据结构和算法,如:列,栈,堆,二分查找,动态规划等。 3.数据结构和算法的关系: 数据结构和算法是相辅相成的。数据结构是为算法服务的,算法是要作用在特定的数据结构上。 三。学习的重点 1....