Java数据结构实现折半查找的算法过程解析

折半查找技术，也就是二分查找，通常称为二分法查找。它的前期是线性表中的记录必须是关键码有序（通常从大到小有序），线性表必须采用顺序存储、折半查找的基本思想是：

取中间记录作为比较对象，若给定值与中间记录的关键字，则在中间记录的关键字相等，则查找成功；若给定值小于中间记录的做半，去继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

在文本排重中需要用到折半查找，需要查找一个数组中是否存在某个数。

算法维护着一个上边界hi，下边界lo，使得要查找的值可能存在此之间，例如，我们要查找88这个数：

初始化数据状态

​

下面图文示意查询88二分法的流程

​

​

​

​

​

​

实现方式：

首先我们对要查找的数据排好序，然后用递归调用的方式实现折半查找，指定一个排好序的数组和要查找的值，同时指定左边界和右边界

/**
* 寻找排好数组中的一个值
*
* @param array 要查找的数组
* @param value 查找的值
* @param left 左边界，这个值必须位于数组长度区间内
* @param right 右边界，这个值必须位于数组长度区间内
* @return 找到的值在数组中的位置，如果没找到就返回-1
*
*/
static int binarySearch(int[] array,int value, int left,int right){
if(left>right){ //退出条件
 return -1; //没有找到指定元素
}
int mid =(left + right) >>>1 ;//相当于mid=(left + right)/2
if(array[mid] == value){
 return mid;
}else if (array[mid] > value){
 //递归调用查找左边
 return binarySearch(array,value,left,mid-1); 

}else {
 //递归调用查找右边
 return binarySearch(array,value,mid+1,right);
}
}

用非递归的方法实现折半查找

static int binarySearch(int[] array,int value, int left,int right){
 int low = left;//开始位置
 int high = right -1; //结束位置
 while(low <= high){
  int mid =(low + high)>>>1; //相当于mid = (low + right)/2
  int midVal = array[mid]; //取中间值
  if(midVal < value){ //中间值小于要查找的关键字比较
   low = mid +1;
  }else if(midVal > value){ //中间值大于要查找的关键字比较
   high = mid -1;
  }else {
   return mid; //查找成功，返回找到的位置
  }
 }
 return -(low+1); //没找到，返回负值
}

需要注意的是：折半查询依赖于排好序的数组。如果是一个没有排好序的数组，则不能使用折半查找。首先需要排序处理。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 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 选择、冒泡排序、折半查找(实例讲解)

    如下所示: //选择排序对数据进行升序排序 public static void selectSortArray(int[] arr){ for(int i = 0; i<arr.length-1;i++){ for(int j = i+1;j<arr.length;j++){ if(arr[i]>arr[j]){ int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } //冒泡排序对数据进行升序排序 public stati

  • java实现折半排序算法

    java实现折半排序算法

    折半插入排序(binary insertion sort)是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中.由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度. public static void halfSort(int[] array) { int low, high, mid; int tmp, j; for (int i = 1; i < array.length; i++) { tm

  • Java实现直接插入排序和折半插入排序算法示例

    Java实现直接插入排序和折半插入排序算法示例

    直接插入排序​ 1 排序思想: 将待排序的记录Ri插入到已经排好序的记录R1,R2,--,R(N-1)中. 对于一个随机序列而言,就是从第二个元素开始,依次将这个元素插入到它之前的元素中的相应位置.它之前的元素已经排好序. 第1次排序:将第2个元素插入到前边的有序列表(此时前边只有一个元素,当然是有序的),之后,这个序列的前2个元素就是有序的了. 第2次排序:将第3个元素插入到前边长度为2的有序列表,使得前2个元素是有序的. 以此类推,直到将第N个元素插入到前面长度为(N-1)的有序列表中. 2

  • 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数据结构实现折半查找的算法过程解析

    折半查找技术,也就是二分查找,通常称为二分法查找.它的前期是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储.折半查找的基本思想是: 取中间记录作为比较对象,若给定值与中间记录的关键字,则在中间记录的关键字相等,则查找成功:若给定值小于中间记录的做半,去继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区继续查找.不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止. 在文本排重中需要用到折半查找,需要查找一个数组中是否存在某个数. 算法维护着一个

  • PHP有序表查找之二分查找（折半查找）算法示例

    本文实例讲述了PHP有序表查找之二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 简介: 二分查找技术,又称为折半查找.它的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须采用顺序存储. 基本思想: 在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功:若给定值小于中间记录的关键字,则在中间记录的左半区继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区继续查找.不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止.

  • Java数据结构彻底理解关于KMP算法

    Java数据结构彻底理解关于KMP算法

    大家好,前面的有一篇文章讲了子序列和全排列问题,今天我们再来看一个比较有难度的问题.那就是大名鼎鼎的KMP算法. 本期文章源码:GitHub源码 简介 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特-莫里斯-普拉特操作(简称KMP算法).KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的.具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息.KMP算法

  • 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实现简单双色球摇奖功能过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 双色球:从1-33号球中选取6个红球,且红球不重复 从1-16号球中选取一个篮球 话不多说 上代码~~~ package Javaee; import java.util.Arrays; import java.util.Random; public class DoubleChromosphere { public static void

  • 使用java NIO及高速缓冲区写入文件过程解析

    使用java NIO及高速缓冲区写入文件过程解析

    这篇文章主要介绍了使用java NIO及高速缓冲区写入文件过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 byte[] bytes = Files.readAllBytes(Paths.get("E:\\pdf\\aaa\\html\\text.txt").normalize()); String text = IOUtils.toString(bytes); String xml = text.substring(

  • java根据富文本生成pdf文件过程解析

    java根据富文本生成pdf文件过程解析

    这篇文章主要介绍了java根据富文本生成pdf文件过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 public class PdfUtil { /* * 生成pdf工具类 * wmy 12:40 2019/8/9 * @Param [guideBook, pdfPath] * @return java.lang.Boolean **/ public static Boolean htmlToPdf(GuideBook guideBook

  • java实现上传文件类型检测过程解析

    这篇文章主要介绍了java实现上传文件类型检测过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 在进行文件上传时,特别是向普通用户开放文件上传功能时,需要对上传文件的格式进行控制,以防止黑客将病毒脚本上传.单纯的将文件名的类型进行截取的方式非常容易遭到破解,上传者只需要将病毒改换文件名便可以完成上传. 可以读取文件的十六进制的文件头,来判断文件真正的格式. 读取文件的二进制数据并将其转换为十六进制时,同类型文件的文件头数据是相同的,即使改

  • Java静态和非静态成员变量初始化过程解析

    这篇文章主要介绍了Java静态和非静态成员变量初始化过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java中非静态成员变量.静态成员变量的初始化时机. 非静态变量 我们在这里分析三种结构,着重分析这三种结构的初始化顺序: 成员变量初始化语句: 成员变量初始化块: 构造函数: 示例一: public class MyTest { private String name = "wei.hu"; public MyTest(Str

  • java使用elasticsearch分组进行聚合查询过程解析

    java使用elasticsearch分组进行聚合查询过程解析

    这篇文章主要介绍了java使用elasticsearch分组进行聚合查询过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 java连接elasticsearch 进行聚合查询进行相应操作 一:对单个字段进行分组求和 1.表结构图片: 根据任务id分组,分别统计出每个任务id下有多少个文字标题 1.SQL:select id, count(*) as sum from task group by taskid; java ES连接工具类 p

随机推荐