java 二分法算法的实例

java 二分法算法的实例

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

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

3、实现：

代码如下


package org.cyxl.algorithm.search; 

/**
 * 二分查找
 * @author cyxl
 *
 */
public class BinarySearch {
  private int rCount=0;
  private int lCount=0; 

  /**
   * 获取递归的次数
   * @return
   */
  public int getrCount() {
    return rCount;
  } 

  /**
   * 获取循环的次数
   * @return
   */
  public int getlCount() {
    return lCount;
  } 

  /**
   * 执行递归二分查找，返回第一次出现该值的位置
   * @param sortedData  已排序的数组
   * @param start     开始位置
   * @param end      结束位置
   * @param findValue   需要找的值
   * @return       值在数组中的位置，从0开始。找不到返回-1
   */
  public int searchRecursive(int[] sortedData,int start,int end,int findValue)
  {
    rCount++;
    if(start<=end)
    {
      //中间位置
      int middle=(start+end)>>1;  //相当于(start+end)/2
      //中值
      int middleValue=sortedData[middle]; 

      if(findValue==middleValue)
      {
        //等于中值直接返回
        return middle;
      }
      else if(findValue<middleValue)
      {
        //小于中值时在中值前面找
        return searchRecursive(sortedData,start,middle-1,findValue);
      }
      else
      {
        //大于中值在中值后面找
        return searchRecursive(sortedData,middle+1,end,findValue);
      }
    }
    else
    {
      //找不到
      return -1;
    }
  } 

  /**
   * 循环二分查找，返回第一次出现该值的位置
   * @param sortedData  已排序的数组
   * @param findValue   需要找的值
   * @return       值在数组中的位置，从0开始。找不到返回-1
   */
  public int searchLoop(int[] sortedData,int findValue)
  {
    int start=0;
    int end=sortedData.length-1; 

    while(start<=end)
    {
      lCount++;
      //中间位置
      int middle=(start+end)>>1;  //相当于(start+end)/2
      //中值
      int middleValue=sortedData[middle]; 

      if(findValue==middleValue)
      {
        //等于中值直接返回
        return middle;
      }
      else if(findValue<middleValue)
      {
        //小于中值时在中值前面找
        end=middle-1;
      }
      else
      {
        //大于中值在中值后面找
        start=middle+1;
      }
    }
    //找不到
    return -1;
  }
}

4、测试代码 

package org.cyxl.algorithm.search.test; 

import org.cyxl.algorithm.search.BinarySearch;
import org.junit.Test; 

public class BinarySearchTest {
  @Test
  public void testSearch()
  {
    BinarySearch bs=new BinarySearch(); 

    int[] sortedData={1,2,3,4,5,6,6,7,8,8,9,10};
    int findValue=9;
    int length=sortedData.length; 

    int pos=bs.searchRecursive(sortedData, 0, length-1, findValue);
    System.out.println("Recursice:"+findValue+" found in pos "+pos+";count:"+bs.getrCount());
    int pos2=bs.searchLoop(sortedData, findValue); 

    System.out.println("Loop:"+findValue+" found in pos "+pos+";count:"+bs.getlCount());
  }
}

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

以上就是java 二分法的实例详解，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • Java二分法查找_动力节点Java学院整理

    算法 假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2. 开始令front=0(指向3),end=7(指向88),则mid=3(指向36).因为mid>x,故应在前半段中查找. 令新的end=mid-1=2,而front=0不变,则新的mid=1.此时x>mid,故确定应在后半段中查找. 令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a

  • java 二分法详解几种实现方法

    java 二分法详解几种方法 二分查找(java实现) 二分查找 算法思想:又叫折半查找,要求待查找的序列有序.每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程.直到查找到了为止,否则序列中没有待查的关键字. 实现: 1.非递归代码 public static int biSearch(int []array,int a){ int lo=0; int hi=array.length

  • Java JDK 二分法 分析demo(推荐)

    如下所示: public class Test { public static void main(String[] args) { Long[] arr = new Long[100000]; for(int i =0;i<100000;i++) { arr[i] = (long) i; } System.out.println(binarySearch(arr, 3L)); Comparable midVal = (Comparable) 2L;; System.out.println(mi

  • java 中二分法查找的应用实例

    java 中二分法查找的应用实例 二分查找的前提是:数组有序 注意:mid的动态变化,否则出错!!! 实例代码: public class BiSearch { public static void main(String[] args) { new BiSearch().biFind(new int []{1,2,3,4,5,6,7},3); } public void biFind(int arr[],int y){ int start=0; int end=arr.length-1; in

  • Java使用二分法进行查找和排序的示例

    实现二分法查找 二分法查找,需要数组内是一个有序的序列 二分查找比线性查找:数组的元素数越多,效率提高的越明显 二分查找的效率表示:O(log2N) N在2的M次幂范围,那查找的次数最大就是M,  log2N表示2的M次幂等于N, 省略常数,简写成O(logN) 如有一个200个元素的有序数组,那么二分查找的最大次数: 2^7=128, 2^8=256, 可以看出7次幂达不到200,8次幂包括, 所以最大查找次数就等于8 //循环,二分查找 static int binarySearch(int

  • java 二分法算法的实例

    java 二分法算法的实例 1.前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2.原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现.所以

  • Java随机数算法原理与实现方法实例详解

    Java随机数算法原理与实现方法实例详解

    本文实例讲述了Java随机数算法.分享给大家供大家参考,具体如下: 软件实现的算法都是伪随机算法,随机种子一般是系统时间 在数论中,线性同余方程是最基本的同余方程,"线性"表示方程的未知数次数是一次,即形如: ax≡b (mod n)的方程.此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除(记作 gcd(a,n) | b).这时,如果 x0 是方程的一个解,那么所有的解可以表示为: {x0+kn/d|(k∈z)} 其中 d 是a 与 n 的最大公约数.在模 n 的完全剩余系

  • java 基本算法之归并排序实例代码

    java 基本算法之归并排序实例代码 原理:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表, * 即把待排序序列分为若干个子序列,每个子序列是有序的.      * 然后再把有序子序列合并为整体有序序列. 实例代码: public class MergeSort { /** * * * * @param args */ public static void main(String[] args) { int a[] = { 49, 38, 65, 97, 76, 13,

  • java排序算法之_选择排序(实例讲解)

    选择排序是一种非常简单的排序算法,从字面意思我们就可以知道,选择就是从未排序好的序列中选择出最小(最大)的元素,然后与第 i 趟排序的第 i-1(数组中下标从 0 开始) 个位置的元素进行交换,第 i 个元素之前的序列就是已经排序好的序列.整个排序过程只需要遍历 n-1 趟便可排好,最后一个元素自动为最大(最小)值. 举个小例子: arr[] = {3,1,2,6,5,4} 第 1 趟排序: index = 0, min = 1, 交换后 -->  1,3,2,6,5,4 第 2 趟排序: in

  • Java 归并排序算法、堆排序算法实例详解

    Java 归并排序算法、堆排序算法实例详解

    基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组

  • java语言实现权重随机算法完整实例

    java语言实现权重随机算法完整实例

    前言 现在app就是雨后春笋,嗖嗖的往外冒啊,有经验的.没经验的.有资历的.没资历的都想着创业,创业的90%以上都要做一个app出来,好像成了创业的标配. 做了app就得推广啊,怎么推,发券送钱是最多用的被不可少的了,现在好多产品或者运营都要求能够随机出优惠券的金额,但是呢又不能过于随机,送出去的券都是钱吗,投资人的钱,是吧. 所以,在随机生成的金额中就要求,小额度的几率要大,大额度的几率要小,比如说3元的70%,5块的25%,10块的5%,这个样子的概率去生成优惠券,这个怎么办呢? 对于上述的

  • Java编程基于快速排序的三个算法题实例代码

    快速排序原理简介 快速排序是我们之前学习的冒泡排序的升级,他们都属于交换类排序,都是采用不断的比较和移动来实现排序的.快速排序是一种非常高效的排序算法,它的实现,增大了记录的比较和移动的距离,将关键字较大的记录从前面直接移动到后面,关键字较小的记录从后面直接移动到前面,从而减少了总的比较次数和移动次数.同时采用"分而治之"的思想,把大的拆分为小的,小的拆分为更小的,其原理如下:对于给定的一组记录,选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,

  • java密钥交换算法DH定义与应用实例分析

    本文实例讲述了java密钥交换算法DH定义与应用.分享给大家供大家参考,具体如下: 一 对称加密缺点 密钥传递过程复杂,这是对称加密带来的困扰. 二 DH密钥交换算法特点 构建本地密钥 双方密钥一致 三 DH相关参数 四 DH算法实现过程 1.初始化发送方的密钥(KeyPairGenerator.KeyPair.PublicKey) 2.初始化接受方的密钥(KeyFactory.X509EncodedKeySpec.DHPublicKey.DHParameterSpec.KeyPairGener

  • Java Base64算法实际应用之邮件发送实例分析

    本文实例讲述了Java Base64算法实际应用之邮件发送.分享给大家供大家参考,具体如下: 一 利用telnet和Base64来实现收发邮件 二 Base64在线编码和解码 http://tools.jb51.net/transcoding/base64 三 Java代码实现 四 运行效果 PS:这里再推荐几款加密解密相关在线工具供大家参考使用: 线编码转换工具(utf-8/utf-32/Punycode/Base64): http://tools.jb51.net/transcoding/d

  • Java实现Shazam声音识别算法的实例代码

    Shazam算法采用傅里叶变换将时域信号转换为频域信号,并获得音频指纹,最后匹配指纹契合度来识别音频. 1.AudioSystem获取音频 奈奎斯特-香农采样定理告诉我们,为了能捕获人类能听到的声音频率,我们的采样速率必须是人类听觉范围的两倍.人类能听到的声音频率范围大约在20Hz到20000Hz之间,所以在录制音频的时候采样率大多是44100Hz.这是大多数标准MPEG-1 的采样率.44100这个值最初来源于索尼,因为它可以允许音频在修改过的视频设备上以25帧(PAL)或者30帧( NTSC

随机推荐