`
IXHONG
  • 浏览: 450251 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Java实现二分查找算法

阅读更多

Java程序员总该玩点基本的算法。

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、总结:这种查找方式的使用场合为已排序的数组。可以发现递归和循环的次数是一样的

0
1
分享到:
评论
1 楼 我的网络世界 2016-10-10  
执行递归二分查找,返回第一次出现该值的位置

其实你并不一定返回的是第一次出现该值的位置 ,比如数组有重复数据,是吧!

相关推荐

    分别使用Java和Python实现二分查找算法

    二分查找:分别使用Java和Python实现二分查找算法 二分查找:分别使用Java和Python实现二分查找算法 二分查找:分别使用Java和Python实现二分查找算法 二分查找:分别使用Java和Python实现二分查找算法 二分查找:...

    Java二分查找递归算法

    Java二分查找递归算法

    Java实现二分查找算法实例分析

    二分查找算法是一种在有序数组中查找特定元素的搜索算法,具有较高的效率。它的核心思想是利用数组的中间元素作为参照,通过比较目标值与中间元素的关系,不断缩小搜索范围,直到找到目标值或者确定目标值不存在。在...

    Java 二分查找 算法

    以下是一个简单的 Java 二分查找算法示例: ```java public class BinarySearchDemo { public static int binarySearch(int[] array, int target) { if (array == null || array.length == 0) { return -1; } ...

    java二分查找算法

    ### Java二分查找算法知识点详解 #### 一、二分查找算法概述 二分查找算法是一种在有序数组中查找特定元素的搜索算法。其工作原理是通过将目标值与数组中间元素进行比较来缩小搜索范围,进而达到快速查找的目的。...

    分别用递归和非递归方法实现二分查找算法 的完整程序

    分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。

    java二分查找实现

    一、Java 二分查找算法的原理 二分查找的原理是将数组分成两个部分,然后在其中一个部分继续进行搜索。假设我们要在数组 `a` 中搜索某个元素 `key`,我们可以将数组分成两个部分,左半部分的元素都小于或等于 `key`...

    Java实现二分查找的递归和非递归算法

    Java实现二分查找的递归和非递归算法

    史上最全,逻辑最清晰的Java经典算法教程:二分查找

    通过学习二分查找算法,不仅可以提高在有序数据集中的搜索效率,而且对于理解和掌握其他更复杂的算法,如归并排序、堆排序等,也有很大帮助。在实际开发中,尤其是在大数据处理、数据库查询等领域,二分查找是不可或...

    Java二分查找算法实现代码实例

    Java二分查找算法实现代码实例 Java二分查找算法实现代码实例主要介绍了Java中的二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值。需要的朋友可以参考下。...

    多种排序查找算法java实现

    这个压缩包文件“多种排序查找算法java实现”显然包含了用Java语言编写的多种经典排序和查找算法的源代码。下面,我们将详细讨论这些算法及其在实际应用中的价值。 首先,我们来看排序算法: 1. **选择排序**:这...

    Java二分查找示例代码

    总结:二分查找算法是计算机科学中的一个重要概念,对于处理有序数据的搜索问题提供了高效的解决方案。Java中的实现直观易懂,便于理解和应用。在实际编程中,结合具体业务需求,我们可以灵活运用二分查找算法来提高...

    算法分析与设计-实验二 二分查找实验报告.docx

    二分查找算法是一种高效的数据搜索方法,主要应用于已排序的序列。它的基本思想是通过不断地将待搜索区域减半来快速定位目标值。这个过程基于分治策略,将大问题分解为更小的子问题来解决。在二分查找算法中,每次...

    java 二分查找法的实现方法

    这段代码中,`binarySearch`函数实现了二分查找算法,`main`函数中给出了一个测试用例。 4. **适用场景**: 二分查找法适用于已排序的数组或列表,如在大量数据中快速定位特定值,或者在数据库索引中查找数据等。...

    二分查找算法实现-修正1

    二分查找算法实现-修正1 二分查找算法是计算机科学中一种常用的查找算法,通过将要查找的数组分成两半,并不断缩小查找范围来找到目标元素。该算法的实现可以在多种编程语言中使用,包括C++、Java、C#等。 在给定...

    java 几种查找算法

    根据给定的文件信息,我们可以总结出几种在Java中实现的...以上算法在Java中的实现涵盖了从简单到复杂的查找技术,包括线性查找、二分查找以及基于树的数据结构查找,为程序员提供了多种选择,以适应不同场景下的需求。

    《二分查找算法》完整版教学设计

    教师采用的教学方法主要是课堂讲授,使用PPT讲解《二分查找算法》的教学设计,引入《二分查找算法》的适用条件和算法思想,并动态展示《二分查找算法》的思想和递归实现。 教学过程 1. 新课导入:教师展示课件,...

    经典Java笔试算法解析和代码:二分查找.zip

    经典Java笔试算法解析和代码:二分查找.zip 经典Java笔试算法解析和代码:二分查找.zip 经典Java笔试算法解析和代码:二分查找.zip 经典Java笔试算法解析和代码:二分查找.zip 经典Java笔试算法解析和代码:二分查找...

    Java排序算法和查找算法

    该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数...查找算法包括:线性查找、二分查找、插值查询、斐波那契(黄金分割法)、

Global site tag (gtag.js) - Google Analytics