`
810364804
  • 浏览: 773560 次
文章分类
社区版块
存档分类
最新评论

数据结构和算法设计专题之---二分查找(Java版)

 
阅读更多

1、前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序

2、原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚,若是不理解可以去网上找。从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现。所以我们的实现分为递归和循环两种,可以根据代码来理解算法

3、实现:代码如下

  1. packageorg.cyxl.algorithm.search;
  2. /**
  3. *二分查找
  4. *@authorcyxl
  5. *
  6. */
  7. publicclassBinarySearch{
  8. privateintrCount=0;
  9. privateintlCount=0;
  10. /**
  11. *获取递归的次数
  12. *@return
  13. */
  14. publicintgetrCount(){
  15. returnrCount;
  16. }
  17. /**
  18. *获取循环的次数
  19. *@return
  20. */
  21. publicintgetlCount(){
  22. returnlCount;
  23. }
  24. /**
  25. *执行递归二分查找,返回第一次出现该值的位置
  26. *@paramsortedData已排序的数组
  27. *@paramstart开始位置
  28. *@paramend结束位置
  29. *@paramfindValue需要找的值
  30. *@return值在数组中的位置,从0开始。找不到返回-1
  31. */
  32. publicintsearchRecursive(int[]sortedData,intstart,intend,intfindValue)
  33. {
  34. rCount++;
  35. if(start<=end)
  36. {
  37. //中间位置
  38. intmiddle=(start+end)>>1;//相当于(start+end)/2
  39. //中值
  40. intmiddleValue=sortedData[middle];
  41. if(findValue==middleValue)
  42. {
  43. //等于中值直接返回
  44. returnmiddle;
  45. }
  46. elseif(findValue<middleValue)
  47. {
  48. //小于中值时在中值前面找
  49. returnsearchRecursive(sortedData,start,middle-1,findValue);
  50. }
  51. else
  52. {
  53. //大于中值在中值后面找
  54. returnsearchRecursive(sortedData,middle+1,end,findValue);
  55. }
  56. }
  57. else
  58. {
  59. //找不到
  60. return-1;
  61. }
  62. }
  63. /**
  64. *循环二分查找,返回第一次出现该值的位置
  65. *@paramsortedData已排序的数组
  66. *@paramfindValue需要找的值
  67. *@return值在数组中的位置,从0开始。找不到返回-1
  68. */
  69. publicintsearchLoop(int[]sortedData,intfindValue)
  70. {
  71. intstart=0;
  72. intend=sortedData.length-1;
  73. while(start<=end)
  74. {
  75. lCount++;
  76. //中间位置
  77. intmiddle=(start+end)>>1;//相当于(start+end)/2
  78. //中值
  79. intmiddleValue=sortedData[middle];
  80. if(findValue==middleValue)
  81. {
  82. //等于中值直接返回
  83. returnmiddle;
  84. }
  85. elseif(findValue<middleValue)
  86. {
  87. //小于中值时在中值前面找
  88. end=middle-1;
  89. }
  90. else
  91. {
  92. //大于中值在中值后面找
  93. start=middle+1;
  94. }
  95. }
  96. //找不到
  97. return-1;
  98. }
  99. }

4、测试代码

  1. packageorg.cyxl.algorithm.search.test;
  2. importorg.cyxl.algorithm.search.BinarySearch;
  3. importorg.junit.Test;
  4. publicclassBinarySearchTest{
  5. @Test
  6. publicvoidtestSearch()
  7. {
  8. BinarySearchbs=newBinarySearch();
  9. int[]sortedData={1,2,3,4,5,6,6,7,8,8,9,10};
  10. intfindValue=9;
  11. intlength=sortedData.length;
  12. intpos=bs.searchRecursive(sortedData,0,length-1,findValue);
  13. System.out.println("Recursice:"+findValue+"foundinpos"+pos+";count:"+bs.getrCount());
  14. intpos2=bs.searchLoop(sortedData,findValue);
  15. System.out.println("Loop:"+findValue+"foundinpos"+pos+";count:"+bs.getlCount());
  16. }
  17. }

5、总结:这种查找方式的使用场合为已排序的数组。可以发现递归和循环的次数是一样的
分享到:
评论

相关推荐

    算法-数据结构和算法-15-二分查找.rar

    算法-数据结构和算法-15-二分查找.rar

    Java数据结构和算法中文第二版

    Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...

    《数据结构与算法》-李春葆 实验报告-典型查找算法实践-二分查找、分块索引查找

    《数据结构与算法》-李春葆 实验报告-典型查找算法实践-二分查找、分块索引查找

    数据结构与排序算法------通过代码示例,讲解:数据结构和9种排序算法。.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    Java数据结构和算法中文第二版(1)

    Java数据结构和算法中文第二版(1) Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择...

    数据结构和算法-Java版.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    java数据结构和算法实践

    常见的算法包括排序算法(如冒泡排序、快速排序)、搜索算法(如二分查找)、图算法(如最短路径算法)等。掌握这些算法的思想和实现方式,可以提高代码的效率和性能。此外,算法设计中的一些基本思想,如递归、动态规划、...

    java数据结构与算法第二版

    递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为...

    基础算法与数据结构 -- Java 实现.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    数据结构查找、排序、二分查找、折半查找算法

    数据结构八大算法,详细介绍了算法的如何实现,以及编码过程,有简单到复杂,由浅入深,看看会有很大收获。

    C语言版数据结构与算法分析-严蔚敏经典视频教程

    01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示与实现、线性表的基本操作 02-003单链表的创建与操作、加工型...

    数据结-构查找算法二分查找二叉顺序数哈希查找

    数据结构-查找算法 二分查找 二叉顺序数 哈希查找

    数据结构 查找算法 源代码

    数据结构 查找 源代码 二分查找的算法源码,两种算法的效率比较

    数据结构之查找算法分析

    讲述了数据结构中的几种查找算法,比如二分查找算法等,分析了其平均长度,时间以及空间开销

    合工大数据结构查找实验

    (1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 (3) 设计算法在...

    Java数据结构和算法中文第二版(2)

    通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择正确的算法 利用数据结构和算法为现实世界的处理过程建模 了解不同的数据结构的优势和弱点,考虑如何利用...

    尚硅谷Java数据结构与java算法(Java数据结构与算法).zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    Java数据结构和算法(第二版)

    递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? ...

    Java数据结构与算法源代码

    指某些著名的数据结构和算法,如:列,栈,堆,二分查找,动态规划等。 3.数据结构和算法的关系: 数据结构和算法是相辅相成的。数据结构是为算法服务的,算法是要作用在特定的数据结构上。 三。学习的重点 1....

Global site tag (gtag.js) - Google Analytics