标签分类
技术文章
当前位置:主页 > 计算机编程 > java > java 二分法算法的实例

java二分法算法的知识点详解

  • 发布时间:
  • 作者:码农之家原创
  • 点击:151

java 二分法算法的实例

这篇文章主要知识点是关于java,二分法,java,二分法的实例,java,二分法实现方法,java 二分法算法的实例,java 中二分法查找的应用实例 的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下电子书

Java Web开发实例大全:提高卷
  • 类型:Java大小:179.4 MB格式:PDF出版:清华大学出版社作者:软件开发技术联盟
立即下载
Java虚拟机基础教程
  • 类型:java大小:78.6 MB格式:PDF出版:人民邮电出版社作者:文森特·范德利昂
立即下载

更多相关的学习资源可以参阅 程序设计电子书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 二分法的实例详解,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

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; 
    int mid=(start+end)/2; 
     
    while(start<=end){ 
      if(y==arr[mid]){ 
            System.out.println("查找成功,其下标为"+mid); 
         break; 
      } 
      if(y>arr[mid]){ 
           start=mid+1; 
           mid=(start+end)/2; 
         } 
      if(y<arr[mid]){ 
           end=mid-1; 
           mid=(start+end)/2; 
        } 
      if(start>end){ 
        System.out.println("查找失败"); 
 
      } 
    } 
  } 
} 

如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

以上就是本次给大家分享的全部知识点内容总结,大家还可以在下方相关文章里找到儿童python编程入门书籍推、 vue项目中使用md5加密以及、 解决axios.interceptors.respon、 等java文章进一步学习,感谢大家的阅读和支持。

上一篇:JNI实现最简单的JAVA调用C/C++实例代码讲解

下一篇:Java获取时间差实例代码详解

展开 +

收起 -

学习笔记
网友NO.111782

java 中冒泡、二分、快速算法详解

1、冒泡算法的原理: 冒泡排序算法的一般性策略:搜索整个值列,比较相邻元素,如果两者的相对次序不对,则交换它们,其结果是最大值“想水泡一样”移动到值列的最后一个位置上,这也是它在最终完成排序的值列中合适的位置。然后再次搜索值列,将第二大的值移动至倒数第二个位置上,重复该过程,直至将所有元素移动到正确的位置上。 下面是两个Java冒泡算法程序 2、冒泡代码如下: public class BubbleSort { public static void bubbleSort(int[] a) { int temp; for (int i = 0; i a.length - 1; ++i) { for (int j = a.length - 1; j i; --j) { if (a[j] a[j - 1]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } } } } public static void main(String[] args) { int a[] = { 49,38,65,97,76,13,27,49}; bubbleSort(a); System.out.println(Arrays.toString(a)); }} 2、二分算法 (1)前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 (2)原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚,若是不理解可以去网上找。从描述……

网友NO.680462

java实现二分法查找出数组重复数字

本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下 package offer;/** * 二分查找的思想来找到数组中重复的数字,时间复杂度在o(nlogn)-o(n^2) */public class FindDuplicate3 { public static void main(String[] args) { int numbers[] = {0,1,2,3,4,4,6,7};//数组中的数 大小从0 到 numbers.length-1 findDuplicate(numbers,0,numbers.length-1); } static void findDuplicate(int numbers[],int left,int right){ if (numbers == null || numbers.length == 0) return; int mid; while(left=right) { System.out.println("Find duplicate from "+left+" to "+right); mid=(left+right)/2; if(left==right)//当两个下标值相等结束循环 { if(countNumberInRange(numbers,left,right)1) { System.out.println(left); break; } else break; } //以下通过计算在指定区间数组中数字的个数与区间的长度对比来确定数组中是否有重复数字 if(countNumberInRange(numbers,left, mid)(mid-left+1))//如果数字区间从left到 mid的数字个数大于mid-left+1 则本区间肯定与重复数字 { right=mid; } else if(countNumberInRange(numbers,mid+1, right)(right-mid))//如果数字区间从mid+1到right的数字个数大于right-mid则本区间肯定有重复数字 { left=mid+1; } else if(countNumberInRange(numbers,left, mid)==(mid-left+1) countNumberInRange(numbers,mid+1, right)==(right-mid)) {//因为上两个判断不能确定区间内是每个数字各出现了一次还是某个数字出现……

网友NO.381140

详解Java数据结构和算法(有序数组和二分查找)

一、概述 有序数组中常常用到二分查找,能提高查找的速度。今天,我们用顺序查找和二分查找实现数组的增删改查。 二、有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三、有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四、代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默认长度 * * @param max */ public OrderArray(int max){ this.a = new long[max]; nElemes = 0; } //查找方法 (二分查找) public int find(long searchElement){ int startIndex = 0; int endIndex = nElemes-1; int curIn; while(true){ curIn = (startIndex + endIndex)/2; if(a[curIn]==searchElement){ return curIn; //找到 }else if(startIndexendIndex){ //沒有找到 return nElemes; //返回大于最大索引整数 }else{ //还要继续找 if(a[curIn]searchElement){ startIndex = curIn + 1; //改变最小索引 }else{ //往前找 endIndex = curIn -1; } } } } //插入元素(线性查找) public void insert(long value){ int j; for(j=0;jnElemes;j++){ if(a[j]value){ break; } } for(int k=nElemes;kj;k--){ a[k] = a[k-1]; } a[j] = value; nElemes++; } //删除数据项 public boolean delete(long value){ int j = find(value); if(j==nElemes){ return false; //没找到 }else{ //所有元素往前移动一位 for(int k=……

网友NO.197009

java算法之二分查找法的实例详解

java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1。通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束。二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组。 Java的简单实现 package me.geed.algorithms; public class BinarySearch { /** * 从一个有序数组(如升序)中找到值为key元素 * @param key * @param array * @return 如果找到目标元素,则返回其在数组中的索引,否则返回-1 */ public static int find(int key, int[] array){ int low = 0; int high = array.length - 1; while (low = high) { int mid = low + (high - low) / 2; if (array[mid] key) { high = mid - 1; } else if (array[mid] key) { low = mid + 1; } else { return mid; } } return -1; } public static void main(String[] args) { // TODO Auto-generated method stub int[] array = {2, 3, 5, 9, 10, 13, 23, 45, 78, 89, 100, 128, 256}; System.out.println("目标元素索引值:" + BinarySearch.find(9, array)); System.out.println("目标元素索引值:" + BinarySearch.find(26, array)); } } 输出……

<
1
>

Copyright 2018-2019 xz577.com 码农之家

版权责任说明