关于二分法查找Java的实现及解析

目录
  • 二分法查找
    • 概述
    • 递归实现
    • 递归实现代码
    • 循环实现代码(非递归)
  • 二分法查找(递归、循环)

二分法查找

概述

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。

但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

归并排序即运用了二分法的思想。首先需要一个由小到大排序好的数组,先对比中间的值,如果比要找的大,则向前找,取中间值前面的一半再找中间值再对比。

如果比要找的小,则向后找,取中间值后面的一半再取中间值再对比。

递归实现

这里,我使用了递归的方法进行实现。

首先需要确认查找的范围,即有一个左索引和右索引,每次取(left+right)/2为中间值,比较要查找的元素和中间值的大小,若中间值大,则向前找,即递归范围为left ,mid-1。反之向右找,即递归范围mid+1,right。若相等即为找到。

但是需要继续向此索引的前后找找看有没有和其相等的值,一并加入到集合中,最后返回这个集合。

递归实现代码

package search;
import java.util.ArrayList;
import java.util.List;
public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1,1,1,2,3,4,5,6,7};
        List<Integer> integers = binarySearch(array, 0, array.length - 1, 1);
//        for (Integer integer : integers) {
//            System.out.print(integer+ " ");
//        }
        System.out.println(integers);
    }
    public static List<Integer> binarySearch(int[] array, int left, int right, int value){
        //如果左索引大于右索引,则说明全部遍历完了,也没有找到相应的值,返回空集合即可
        if (left>right){
            return new ArrayList<Integer>();
        }
        //获取中间值的下标(二分)
        int mid = (left+right)/2;
        //如果要找的值比中间值小,则继续向左找
        if (value < array[mid]){
            return binarySearch(array, left, mid-1, value);
        //要找的值比中间值小大,则向右找
        }else if (value > array[mid]){
            return binarySearch(array, mid+1, right, value);
        //否则,说明相等,找到了
        }else {
            //找到一个,还需要向左右找找看有没有相同的值
            List<Integer> resultList = new ArrayList();
            //向左循环找,如果有,则加入到集合中
            int temp = mid - 1;
            while (temp>=0 && array[temp] == value){
                resultList.add(temp);
                temp -= 1;
            }
            //向右循环找,如果有,则加入到集合中
            temp = mid + 1;
            while (temp < array.length && array[temp] == value){
                resultList.add(temp);
                temp += 1;
            }
            //将一开始找到的那个索引页加入到集合中。
            resultList.add(mid);
            return resultList;
        }
    }

    //以下这段代码来自百度百科,供大家参考。
    public static int binarySearch(Integer[] srcArray, int des) {
        //定义初始最小、最大索引
        int start = 0;
        int end = srcArray.length - 1;
        //确保不会出现重复查找,越界
        while (start <= end) {
            //计算出中间索引值
            int middle = (end + start)>>>1 ;//防止溢出
            if (des == srcArray[middle]) {
                return middle;
                //判断下限
            } else if (des < srcArray[middle]) {
                end = middle - 1;
                //判断上限
            } else {
                start = middle + 1;
            }
        }
        //若没有,则返回-1
        return -1;
    }
}

循环实现代码(非递归)

package search;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * @Author: sshdg
 * @Date: 2020/9/21 9:22
 */
public class BinarySearch2 {
    public static void main(String[] args) {
        int[] array = {1,1,1,1,1,2,3,4,5,6,7};
        System.out.println(BinarySearch2.binarySearch(array, 7));
    }
    public static List<Integer> binarySearch(int[] array, int key){
        List<Integer> resultList = new ArrayList<>();
        int start = 0;
        int end = array.length - 1;
        while (start <= end){
            int mid = (start + end) / 2;
            int midValue = array[mid];
            if (key > midValue){
                //key比中间值大。向右找
                start = mid + 1;
            } else if (key < midValue){
                //key比中间值小。向左找
                end = mid - 1;
            } else {
                //否则就找到了
                //先向左找有没有相同值
                int temp = mid -1;
                while (temp >= start && array[temp] == key){
                    resultList.add(temp);
                    temp -= 1;
                }
                //将一开始找到的加入结果集
                resultList.add(mid);
                //再向右找找有没有相同值
                temp = mid + 1;
                while (temp <= end && array[temp] == key){
                    resultList.add(temp);
                    temp += 1;
                }
                break;
            }
        }
        return resultList;
    }
}

二分法查找(递归、循环)

public class BinarySearch {
    /**
     * @author JadeXu
     * @// TODO: 2020/12/7 二分查找
     * 思路:
     * 1、获取数组的中间值,先获取下标,方便多次查找
     * 奇数位的数组直接获取中间位,偶数位的数组获取中间的第一位或第二位都可,一般获取第一位(因为与奇数位获取中间值的方法一样)
     * 2、获取查找的区间范围,start:区间开始的下标,end:区间结束的下标
     * 3、判断查找的数和中间位的数是否相同
     * 相同时,直接返回需要的数据,跳出方法
     * 大于时,即数可能在中间值右边的区间内,此时start = mid+1,即mid往后移一位,就得到了中间值右边区间的开始下标
     * 小于时,即数可能在中间值左边的区间内,此时end = mid-1,即mid往前移一位,就得到了中间值左边区间的结束下标
     * 当一个区间里,开始下标小于等于结束下标时,该区间才是有效区间,才能继续查找。否则无效,返回找不到,跳出方法
     */
    //循环
    /**
     * @param arr 已经升序好的int[]
     * @param num 需要查找的数字
     * @return 找到则返回下标,没找到则返回-1
     */
    private static int binarySearchByCycle(int[] arr,int num) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end){
            int mid = (start + end) / 2;
            if(num == arr[mid]){
                return mid;
            }else if(num > arr[mid]){
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        return -1;
    }
    //递归
    /**
     * @param arr 已经升序好的int[]
     * @param num 需要查找的数字
     * @param start 区间开始下标
     * @param end 区间结束下标
     * @return 找到则返回下标,没找到则返回-1
     */
    private static int binarySearchByRecursion(int[] arr,int num,int start,int end) {
        int mid = (start + end) / 2;
        if(num == arr[mid]){
            return mid;
        }else if(num > arr[mid]){
            start = mid + 1;
        }else {
            end = mid - 1;
        }
        if(start <= end){
            mid = binarySearchByRecursion(arr,num,start,end);  //递归继续寻找
        }else {
            mid = -1;
        }
        return mid;
    }
}

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • 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学院整理

    算法 假如有一组数为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实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下 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使用二分法进行查找和排序的示例

    实现二分法查找 二分法查找,需要数组内是一个有序的序列 二分查找比线性查找:数组的元素数越多,效率提高的越明显 二分查找的效率表示: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的实现及解析

    目录 二分法查找 概述 递归实现 递归实现代码 循环实现代码(非递归) 二分法查找(递归.循环) 二分法查找 概述 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法. 但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列. 归并排序即运用了二分法的思想.首先需要一个由小到大排序好的数组,先对比中间的值,如果比要找的大,则向前找,取中间值前面的一半再找中间值再对比. 如果比要找的小,则向后找,取中间值后面的一半再取中间值再对比. 递归实现 这里,

  • 解析php二分法查找数组是否包含某一元素

    二分法查找数组是否包含某一元素,兼容正反序,代码实现: 复制代码 代码如下: <?php $searchValue = (int)$_GET['key']; function search(array $array, $value) {     $max = count($array)-1;     $min = 0;     $isAscSort = $array[$min] < $array[$max]; while (TRUE) {         $sum = $min+$max;  

  • java TreeMap源码解析详解

    java TreeMap源码解析详解 在介绍TreeMap之前,我们来了解一种数据结构:排序二叉树.相信学过数据结构的同学知道,这种结构的数据存储形式在查找的时候效率非常高. 如图所示,这种数据结构是以二叉树为基础的,所有的左孩子的value值都是小于根结点的value值的,所有右孩子的value值都是大于根结点的.这样做的好处在于:如果需要按照键值查找数据元素,只要比较当前结点的value值即可(小于当前结点value值的,往左走,否则往右走),这种方式,每次可以减少一半的操作,所以效率比较高

  • Java String创建对象实例解析

    本文研究的主要是Java String创建对象的问题,具体介绍如下. 首先我们要明白两个概念,引用变量和对象,对象一般通过new在堆中创建,String只是一个引用变量. 所有的字符串都是String对象,由于字符串常量的大量使用,java中为了节省时间,在编译阶段,会把所有字符串常量放在字符串常量池中,字符串常量池的一个好处就是可以把相同的字符串合并,占用一个空间. 虽然在Java中无法直接获取变量的地址,但是可以用==判断一下两个引用变量是否指向了一个地址即一个对象. 栈内存 堆内存 基础类

  • 浅谈二分法查找和原始算法查找的效率对比

    我就废话不多说了,大家还是直接看代码吧! import java.text.MessageFormat; public class AppTest { static int length = 70000000; static int[] array = new int[length]; static { for (int i = 0; i < length; i++) { array[i] = i; } } public static void main(String[] args) { for

  • Java数据结构二叉树难点解析

    前言 本章,我们主要需要了解以下内容 什么是线索二叉树 怎么去把二叉树线索化 怎么通过线索二叉树查找某个数的后继结点 二叉树的查看--二叉树怎们遍历 什么是线索二叉树 首先我们来了解一下什么是线索二叉树? 定义:一个二叉树通过如下的方法"穿起来":所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继,所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱. 再看一下为什么要有线索二叉树? 顾名思义,线索二叉树,肯定是根据线索查找,查找速度肯定更快. 线索二叉树能线性地遍历二

  • Java Spring 循环依赖解析

    目录 1.常见问题 2.什么是循环依赖? 3.循环依赖说明 4.BeanCurrentlyInCreationException 5.依赖注入的两种方式 方式一:构造器方式注入依赖 方式二:以 set 方式注入依赖 6.Spring 三级缓存介绍和循环依赖解决过程 三级缓存介绍 实例化/初始化定义 三级缓存使用过程 A/B 两对象在三级缓冲的迁移说明 ObjectFactory 接口 DEBUG 断点调试 循环依赖解决 7.Spring 循环依赖总结 1.常见问题 你解释一下 spring 中的

随机推荐