文档章节

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

我爱睡觉
 我爱睡觉
发布于 2017/06/24 16:36
字数 718
阅读 0
收藏 0

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

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

3、实现:代码如下

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

4、测试代码

[java]  view plain copy
  1. package org.cyxl.algorithm.search.test;  
  2.   
  3. import org.cyxl.algorithm.search.BinarySearch;  
  4. import org.junit.Test;  
  5.   
  6.   
  7. public class BinarySearchTest {  
  8.     @Test  
  9.     public void testSearch()  
  10.     {  
  11.         BinarySearch bs=new BinarySearch();  
  12.           
  13.         int[] sortedData={1,2,3,4,5,6,6,7,8,8,9,10};  
  14.         int findValue=9;  
  15.         int length=sortedData.length;  
  16.           
  17.         int pos=bs.searchRecursive(sortedData, 0, length-1, findValue);  
  18.         System.out.println("Recursice:"+findValue+" found in pos "+pos+";count:"+bs.getrCount());  
  19.         int pos2=bs.searchLoop(sortedData, findValue);  
  20.           
  21.         System.out.println("Loop:"+findValue+" found in pos "+pos+";count:"+bs.getlCount());  
  22.     }  
  23. }  

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

本文转载自:http://blog.csdn.net/jiangwei0910410003/article/details/38024403

我爱睡觉
粉丝 3
博文 2120
码字总数 0
作品 0
南昌
私信 提问
如何理解并掌握 Java 数据结构

一说起“数据结构”可能很多同学都又交给老师了。但是实际工作中如果做得深入一些,特别是越往上发展,越大公司越离不开数据结构。本场 Chat 作者将带领大家重温《Java 数据结构》,讲解的内...

valada
2018/04/12
0
0
RichFaces自动构建树实现

树形结构在软件系统中是使用频率非常大的一种数据结构,包括一些算法的实现也是基于树形结构来进行的,比如基于二叉树的二分查找法等等。在软件系统中,树形结构更多的体现在树形菜单的构建上...

菜根乱谭
2009/10/08
250
0
1-玩转数据结构-欢迎学习数据结构

欢迎大家学习新课程: 玩转数据结构 为什么要学习数据结构? 数据结构是所有计算机专业的同学必学的课程 数据结构研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据或者...

天涯明月笙
2018/08/10
0
0
【JDK7】新特性(5) fork/join 框架

对于框架的原理,可以阅读 Doug Lea 的文章“A Java Fork/Join Framework”:了解 Fork/Join 模式的实现机制和执行性能。 原理解析:fork分解,join结合。这个框架的本质是将一个任务分解成多...

5W1H-
2012/12/11
0
0
面试必看!2018年4月份阿里最新的java程序员面试题目

目录 技术一面(23问) 技术二面(3大块) 性能优化(21点) 项目实战(34块) JAVA方向技术考察点(15点) JAVA开发技术面试中可能问到的问题(17问) 阿里技术面试1 1.Java IO流的层次结构...

美的让人心动
2018/04/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

词法分析器flex教程

词法分析器flex教程 flex是基于正则表达式,用于对字符串进行提取和分析的工具。一般情况下,flex常用语编译器前端的词法分析阶段。flex程序读取用户输入的词法单元描述文件,生成lex.yy.c文...

陶小陶
21分钟前
1
0
IntelliJ IDEA 社区版没有 Spring Initializr

RT 解决办法 打开文件 - 设置 - 插件 输入 Spring 找到插件 Spring Assistant 并安装 下载可能会需要一点点时间 . 重启 IDEA 后,新建项目就可以看见 Spring Assistant 选项了...

taadis
24分钟前
0
0
MySQL执行计划 type类型

MySql提供了EXPLAIN语法用来进行查询分析,在SQL语句前加一个"EXPLAIN"即可。 explain select * from t_settlement_settle_order_detail where id = 2; 下面来介绍各个字段: type:连接类型......

ChyiHuang
27分钟前
1
0
mysql遇到的坑

sql_mode=NO_ENGINE_SUBSTITUTION 今天在测试库上发现使用GROUP BY 报错,我使用的mysql5.7 ONLY_FULL_GROUP_BY 对于GROUP BY聚合操作,如果在SELECT中的列、HAVING或者ORDER BY子句的列,没...

事儿爹
39分钟前
1
0
聊聊flink的InternalTimeServiceManager

序 本文主要研究一下flink的InternalTimeServiceManager InternalTimeServiceManager flink-streaming-java_2.11-1.7.0-sources.jar!/org/apache/flink/streaming/api/operators/InternalTim......

go4it
51分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部