文档章节

数据结构和算法设计专题之---二分查找(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
04/12
0
0
RichFaces自动构建树实现

Java代码 public class TreeNode{ private String value;//树节点的值 private String label;//树节点显示标签 private bo ... [阅读全文] JavaEye推荐 【杭州】高薪招聘控件高级开发工程师(...

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

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

天涯明月笙
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流的层次结构...

美的让人心动
04/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

快速get到学习Linux操作系统的点

Linux是一套免费使用和自由传播的类Unix操作系统,是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。Linux能够运行主要的UNIX工具软件、网络协议和应用程序。它支持32位...

linux-tao
11分钟前
0
0
Docker Compose 之进阶篇

前文《Docker Compose 简介》和《Dcoker Compose 原理》两篇文章中分别介绍了 docker compose 的基本概念以及实现原理。本文我们将继续探索 docker compose,并通过 demo 介绍一些主要的用法...

Java干货分享
17分钟前
0
0
《netty入门与实战》笔记-04:pipeline 与 channelHandler

这一小节,我们将会学习 Netty 里面一大核心组件: Pipeline 与 ChannelHandler Netty 中的 pipeline 和 channelHandler 通过责任链设计模式来组织代码逻辑,并且能够支持逻辑的动态添加和删...

Funcy1122
22分钟前
0
0
知识积累

####知识积累 Q:What is the bit depth of a JPEG? A:JPEG is standardized as an 8-bit image file. This means that each color channel of a pixel has 8-bits of data allocated to repr......

-___-
34分钟前
0
0
shell学习之创建函数

函数是一个脚本代码块,你可以为其命名并在代码中任何位置重用。 在bash shell脚本中创建函数基本使用如下两种方式,第二种格式更接近于其他编程语言中定义函数的方式。 function name {com...

woshixin
46分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部