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[] array, int data) {
  int start = 0;
  int end = array.length - 1;
  int mid = -1;
  while (start <= end) {
   System.out.println("查找次数");
   mid = (start + end) >>> 1;
   if (array[mid] < data) {
    start = mid + 1;
   } else if (array[mid] > data) {
    end = mid - 1;
   } else {
    return mid;
   }
   System.out.println("start=" + start+",end="+end+",mid="+mid);
  }
  return -1;
 }
//递归二分查找 初始start=0, end = array.length - 1
 static int binarySearch4Recursion(int[] array, int data, int start, int end) {
  int mid = -1;
  System.out.println("查找次数");
  if (start > end) {
   return mid;
  }
  mid = (start + end) >>> 1;
  if (array[mid] < data) {
   return binarySearch4Recursion(array, data, mid + 1, end);
  } else if (array[mid] > data) {
   return binarySearch4Recursion(array, data, start, mid - 1);
  } else {
   return mid;
  } 

 } 

二分法插入排序

设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置
效率:O(N^2),对于初始基本有序的序列,效率上不如直接插入排序;对于随机无序的序列,效率比直接插入排序要高

/*
 * 二分(折半)插入排序
 * 设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置
 */
public class BinaryInsertSort { 

 public static void main(String[] args) {
  int len = 10;
  int[] ary = new int[len];
  Random random = new Random();
  for (int j = 0; j < len; j++) {
   ary[j] = random.nextInt(1000);
  }
  binaryInsert(ary);
  /*
   * 复杂度分析: 最佳情况,即都已经排好序,则无需右移,此时时间复杂度为:O(n lg n) 最差情况,全部逆序,此时复杂度为O(n^2)
   * 无法将最差情况的复杂度提升到O(n|logn)。
   */
  // 打印数组
  printArray(ary);
 }
 /**
  * 插入排序
  * @param ary
  */
 private static void binaryInsert(int[] ary) {
  int setValueCount = 0;
  // 从数组第二个元素开始排序,因为第一个元素本身肯定是已经排好序的
  for (int j = 1; j < ary.length; j++) {// 复杂度 n
   // 保存当前值
   int key = ary[j];
   // ∆ 利用二分查找定位插入位置
//   int index = binarySearchAsc(ary, ary[j], 0, j - 1);// 复杂度:O(logn)
//   int index = binarySearchDesc(ary, ary[j], 0, j - 1);// 复杂度:O(logn)
   int index = binarySearchDesc2(ary, ary[j], 0, j - 1);// 复杂度:O(logn)
   printArray(ary);
   System.out.println("第" + j +"个索引上的元素要插入的位置是:" + index);
   // 将目标插入位置,同时右移目标位置右边的元素
   for (int i = j; i > index; i--) {// 复杂度,最差情况:(n-1)+(n-2)+...+n/2=O(n^2)
    ary[i] = ary[i - 1]; //i-1 <==> index
    setValueCount++;
   }
   ary[index] = key;
   setValueCount++;
  }
  System.out.println("\n 设值次数(setValueCount)=====> " + setValueCount);
 } 

 /**
  * 二分查找 升序 递归
  *
  * @param ary
  *   给定已排序的待查数组
  * @param target
  *   查找目标
  * @param from
  *   当前查找的范围起点
  * @param to
  *   当前查找的返回终点
  * @return 返回目标在数组中,按顺序应在的位置
  */
 private static int binarySearchAsc(int[] ary, int target, int from, int to) {
  int range = to - from;
  // 如果范围大于0,即存在两个以上的元素,则继续拆分
  if (range > 0) {
   // 选定中间位
   int mid = (to + from) / 2;
   // 如果临界位不满足,则继续二分查找
   if (ary[mid] > target) {
    /*
     * mid > target, 升序规则,target较小,应交换位置 前置, 即target定位在mid位置上,
     * 根据 查找思想, 从from到 mid-1认为有序, 所以to=mid-1
     */
    return binarySearchAsc(ary, target, from, mid - 1);
   } else {
    /*
     * mid < target, 升序规则,target较大,不交换位置,查找比较的起始位置应为mid+1
     */
    return binarySearchAsc(ary, target, mid + 1, to);
   }
  } else {
   if (ary[from] > target) {//如 5,4, 要插入的是4
    return from;
   } else {
    return from + 1;
   }
  }
 }
 /**
  * 二分查找 降序, 递归
  */
 private static int binarySearchDesc(int[] ary, int target, int from, int to) {
  int range = to - from;
  if (range > 0) {
   int mid = (from + to) >>> 1;
   if (ary[mid] > target) {
    return binarySearchDesc(ary, target, mid + 1, to);
   } else {
    return binarySearchDesc(ary, target, from, mid - 1);
   }
  } else {
   if (ary[from] > target) {//如 5,4, 要插入的是4
    return from + 1;
   } else {
    return from;
   }
  }
 } 

 /**
  * 二分查找 降序, 非递归
  */
 private static int binarySearchDesc2(int[] ary, int target, int from, int to) {
//  while(from < to) {
  for (; from < to; ) {
   int mid = (from + to) >>> 1;
   if (ary[mid] > target) {
    from = mid + 1;
   } else {
    to = mid -1;
   }
  }
  //from <==> to;
  if (ary[from] > target) {//如 5,4, 要插入的是4
   return from + 1;
  } else {
   return from;
  }
 } 

 private static void printArray(int[] ary) {
  for (int i : ary) {
   System.out.print(i + " ");
  }
 } 

}

打印

918 562 442 531 210 216 931 706 333 132 第1个索引上的元素要插入的位置是:1
918 562 442 531 210 216 931 706 333 132 第2个索引上的元素要插入的位置是:2
918 562 442 531 210 216 931 706 333 132 第3个索引上的元素要插入的位置是:2
918 562 531 442 210 216 931 706 333 132 第4个索引上的元素要插入的位置是:4
918 562 531 442 210 216 931 706 333 132 第5个索引上的元素要插入的位置是:4
918 562 531 442 216 210 931 706 333 132 第6个索引上的元素要插入的位置是:0
931 918 562 531 442 216 210 706 333 132 第7个索引上的元素要插入的位置是:2
931 918 706 562 531 442 216 210 333 132 第8个索引上的元素要插入的位置是:6
931 918 706 562 531 442 333 216 210 132 第9个索引上的元素要插入的位置是:9

设值次数(setValueCount)=====> 24

931 918 706 562 531 442 333 216 210 132

(0)

相关推荐

  • Java经典算法汇总之顺序查找(Sequential Search)

    a)原理:顺序查找就是按顺序从头到尾依次往下查找,找到数据,则提前结束查找,找不到便一直查找下去,直到数据最后一位. b)图例说明: 原始数据:int[]a={4,6,2,8,1,9,0,3}; 要查找数字:8 找到数组中存在数据8,返回位置. 代码演示: import java.util.Scanner; /* * 顺序查找 */ public class SequelSearch { public static void main(String[] arg) { int[] a={4,6,2

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

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

  • java二分查找插入法

    复制代码 代码如下: package uv; public class Bean  implements Comparable<Bean>  {String sessionId;Integer num = 1;public String getSessionId() {return sessionId;}public void setSessionId(String sessionId) {this.sessionId = sessionId;}public Integer getNum()

  • Java实现的两种常见简单查找算法示例【快速查找与二分查找】

    本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng

  • java 折半查找法(二分查找)实例

    复制代码 代码如下: public class HalfSearch { public static int halfSearch(int a[], int x) {  int mid, left, right;  left = 0;  right = a.length - 1;   mid = (left + right) / 2;  while (a[mid] != x) {   if (x > a[mid]) {    left = mid + 1;   }   else if (x <

  • Java正则表达式实现在文本中匹配查找换行符的方法【经典实例】

    本文实例讲述了Java正则表达式实现在文本中匹配查找换行符的方法.分享给大家供大家参考,具体如下: 默认情况下,正则表达式 ^ 和 $ 忽略行结束符,仅分别与整个输入序列的开头和结尾匹配.如果激活 MULTILINE 模式,则 ^ 在输入的开头和行结束符之后(输入的结尾)才发生匹配.处于 MULTILINE 模式中时,$ 仅在行结束符之前或输入序列的结尾处匹配. NLMatch.java: package nlMatch; import java.util.regex.Pattern; /**

  • Java实现的快速查找算法示例

    本文实例讲述了Java实现的快速查找算法.分享给大家供大家参考,具体如下: 快速查找算法,可以根据想要找的是第几个大的数,每次循环都能固定下来一个数在数组完整排完序之后的位置,每次循环都能定一个数的位置,如果当前固定的数的位置和用户要找的第几个数匹配,则就直接返回.例如我要找第二大的数,如果循环一次固定的数的下标是1,那就是当前需要找的数. 代码如下: // 快速查找算法 public static int quickSelect(int[] arr, int selectIndex) { in

  • java 算法二分查找和折半查找

     java 算法二分查找与折半查找 折半查找 :首先数组是已经排好序的 实例代码: package com.hao.myrxjava; /** * 折半查找 :首先数组是已经排好序的 * * @author zhanghaohao * @date 2017/5/15 */ public class HalfDivision { /** * 循环实现 * * @param array 排好序的数组 * @param value 查找的值 * @return value在array的位置 */ pu

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

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • 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实现ArrayList根据存储对象排序功能示例

    本文实例讲述了java实现ArrayList根据存储对象排序功能.分享给大家供大家参考,具体如下: 与c++中的qsort的实现极为相似,构建新的比较对象Comparator即可 package demo; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; class Stu{ public int age; private String name; public Stu(

  • java实现对map的字典序排序操作示例

    本文实例讲述了java实现对map的字典序排序操作.分享给大家供大家参考,具体如下: java中对map的字典序排序,算法验证比对微信官网https://mp.weixin.qq.com/wiki?t=resource/res_main&id=mp1421141115&token=&lang=zh_CN,搜索关键字"附录1-JS-SDK使用权限签名算法" import java.util.ArrayList; import java.util.Collectio

  • java教程之二个arraylist排序的示例分享

    示例1 复制代码 代码如下: package com.yonyou.test;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;public class Test { public static void main(String[] args) {  Student zlj = new Student("丁晓宇", 21); 

  • 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实现二分法查找出数组重复数字

    本文实例为大家分享了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 f

  • 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中二分法的基本思路和实现

    目录 在一个有序数组中,找某个数是否存在 在一个有序数组中,找大于等于某个数最左侧的位置 在排序数组中查找元素的第一个和最后一个位置 局部最大值问题 在一个有序数组中,找某个数是否存在 思路: 由于是有序数组,可以先得到中点位置,中点可以把数组分为左右半边. 如果中点位置的值等于目标值,直接返回中点位置. 如果中点位置的值小于目标值,则去数组中点左侧按同样的方式寻找. 如果中点位置的值大于目标值,则取数组中点右侧按同样的方式寻找. 如果最后没有找到,则返回:-1. 代码 class Soluti

  • java数据结构之二分查找法 binarySearch的实例

    java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.

  • java数据结构与算法之桶排序实现方法详解

    本文实例讲述了java数据结构与算法之桶排序实现方法.分享给大家供大家参考,具体如下: 基本思想: 假定输入是由一个随机过程产生的[0, M)区间上均匀分布的实数.将区间[0, M)划分为n个大小相等的子区间(桶),将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <M辅助数组B[0..n-1]是一指针数组,指向桶(链表).将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. [桶-

随机推荐