Java 二分查找的实现及图例解析

二分查找又称折半查找，它是一种效率较高的查找方法。

折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。

折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

二分算法步骤描述：

1.确定整个查找区间的中间位置 mid = （ left + right ）/ 2

2.用待查关键字值与中间位置的关键字值进行比较；

若相等，则查找成功

若大于，则在后（右）半个区域继续进行折半查找

若小于，则在前（左）半个区域继续进行折半查找

3.对确定的缩小区域再按折半公式，重复上述步骤。

4.得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。 折半查找算法举例

注意：查找失败（即在查找内容中没有你要找的），这时控制台并不会报错。

代码实例：

package com.shuzu;

public class Demo7 {

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    // 测试，数组(有序，以升序序列为例。这里是园友留言，提示纠正的。)
    int arr[] = { 1, 3, 4, 7, 11, 16, 33, 43, 65, 77, 88, 90, 99, 110 };

    BinaryFind bf = new BinaryFind();
    bf.find(0, arr.length - 1, 33, arr);
  }
}

// 定义一个二分查找的类
class BinaryFind {
  public void find(int leftIndex, int rightIndex, int val, int arr[]) {
    // 首先找到中间的数，这里不用担心。/代表取整。    //（之前的错误，被园友纠正：Java中，除不尽会自动取整）
    int midIndex = (rightIndex + leftIndex) / 2;
    int midVal = arr[midIndex];

    if (rightIndex >= leftIndex) {
      // 如果要找的数比midVal大
      if (midVal > val) {
        // 在arr数组的左边找
        find(leftIndex, midIndex - 1, val, arr);
      } else if (midVal < val) {
        // 在arr数组的右边找
        find(midIndex + 1, rightIndex, val, arr);
      } else if (midVal ==val) {
        System.out.println("找到下标" + midIndex);
      }
    }
  }
}

图例演示原理：

以上就是Java 二分查找的实现的详细内容，更多关于Java 二分查找的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 详解Java数据结构和算法（有序数组和二分查找）

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

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

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

  • 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二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 二分查找: 两种方式: 非递归方式和递归方式 主要思路: 对于已排序的数组(先假定是从小到大排序), 先定义两个"指针", 一个"指向"首元素low, 一个"指向"末尾元素high. 然后, 开始折半比较, 即让要查找的数与数组中间的元素(索引为 low+high/2)比较. 若要查找的数比中间数小

  • JAVA冒泡排序和二分查找的实现

    JAVA冒泡排序和二分查找的实现

    冒泡排序  冒泡排序(Bubble Sort),看到这种算法,我就想起一句话"小数上浮,大数下沉",通过层层的比较使小数浮出水面,而使大数"石沉水底".从而达到排序的效果.冒泡排序是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序算法的运作如下

  • Java实现二分查找的变种

    Java实现二分查找的变种

    本文实例为大家分享了Java实现二分查找的变种,供大家参考,具体内容如下 普通二分查找: 先回顾一下普通的二分查找 注意:二分查找有这样一个问题:当数组中数有重复时,比如 {3,3,3,3} 这个数组,二分查找3时,返回的是arr[1],也就是说二分查找并不会返回3第一次出现的位置0. public class BinarySearch { public static <T extends Comparable<? super T>> int search(T arr[], T v

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

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

  • 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 二分查找的实现及图例解析

    Java 二分查找的实现及图例解析

    二分查找又称折半查找,它是一种效率较高的查找方法. 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分.通过一次比较,将查找区间缩小一半. 折半查找是一种高效的查找方法.它可以明显减少比较次数,提高查找效率.但是,折半查找的先决条件是查找表中的数据元素必须有序. 折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除

  • Java二分查找算法与数组处理的应用实例

    Java二分查找算法与数组处理的应用实例

    目录 1.特殊数组的特征值 题目描述 思路详解 代码与结果 2.在D天内送达包裹的能力 题目描述 思路详解 代码与结果 3.咒语和药水的成功对数 题目描述 思路详解 代码与结果 总结 1.特殊数组的特征值 题目描述 思路详解 看到本题,首先思考需要排序,然后查找,这里为了效率采用二分查找. 假设定义x=(left+riht)/ 2,每次查找到nums中第一个大于等于X的元素下标,判断大于等于X的个数与X的关系,进行分情况修改左右边界. 代码与结果 class Solution { public

  • 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实现二分查找树及其相关操作

    二分查找树(Binary Search Tree)的基本操作有搜索.求最大值.求最小值.求前驱.求后继.插入及删除. 对二分查找树的进行基本操作所花费的时间与树的高度成比例.例如有n个节点的完全二叉树,对它进行的基本操作的时间复杂度为O(logn).然而,如果树是一个有n个节点的线性的链,则在这种情况下的时间复杂度为O(n). 1.什么是二分查找树 二分查找树是一种有组织的二叉树.我们可以通过链接节点表示这样一棵树.每个节点包含键(key),数据(data),左子节点(left),右子节点(ri

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

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

随机推荐