文档章节

数据结构和算法设计专题之---二分查找(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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

基于TP5的微信的公众号获取登录用户信息

之前讲过微信的公众号自动登录的菜单配置,这次记录一下在TP5项目中获取自动登录的用户信息并存到数据库的操作 基本的流程为:微信设置自动登录的菜单—>访问的URL指定的函数里获取用户信息—...

月夜中徘徊
今天
0
0
youTrack

package jetbrains.teamsys.license.runtime; 计算lis package jetbrains.ring.license.reader; 验证lis 安装后先不要生成lis,要把相关文件进行替换 ring-license-checker-1.0.41.jar char......

max佩恩
今天
0
0
12.17 Nginx负载均衡

Nginx负载均衡 下面的dig看到可以返回2个IP,就是解析出来的IP,这样我们可以做负载均衡。 dig www.qq.com 1.vim /usr/local/nginx/conf/vhost/fuzai.conf 2.添加如下配置 upstream qq //定义...

芬野de博客
今天
0
0
SSE(Server Send Event 服务端发送事件)

package com.example.demo.controller;import org.springframework.stereotype.Controller;import org.springframework.web.bind.annotation.RequestMapping;import org.springframe......

Canaan_
今天
0
0
jvm调优

1.jvm运行模式 client模式:启动快,占用内存少,jit编译器生成代码的速度也更快. server模式:主要优势在于代码优化功能,这个功能对于服务器应用而言尤其重要. tiered server模式:结合了client与...

Funcy1122
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部