精华内容
下载资源
问答
  • Java实现二分查找算法(非递归)
    千次阅读
    2021-10-11 10:43:05

    14.1 二分查找算法(非递归)

    14.1.1 二分查找算法(非递归)介绍

    1. 之前发过二分查找算法,是使用递归的方式,下面我们用二分查找算法的非递归方式
    2. 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找
    3. 二分查找法的运行时间为对数时间 O(㏒₂n) ,即查找到需要的目标位置最多只需要㏒₂n 步,假设从[0,99]的队列(100 个数,即 n=100)中寻到目标数 30,则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)

    14.1.2 二分查找算法(非递归)代码实现

    数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找, 要求使用非递归的方式完成。

    代码实现

    /**
     * @author zk
     * @version 1.0.0
     * @ClassName BinarySearchNoRecur.java
     * @Description TODO 二分查找算法(非递归)
     * @createTime 2021年09月29日 14:52:00
     */
    public class BinarySearchNoRecur {
        public static void main(String[] args) {
            //测试
            int[] arr = {1,3, 8, 10, 11, 67, 100};
            int i = binarySearch(arr, 67);
            System.out.println(i);
        }
        //二分查找的非递归实现
        /**
         *
         * @param arr 待查找的数组, arr 是升序排序
         * @param target 需要查找的数
         * @return 返回对应下标,-1 表示没有找到
         */
        public static int binarySearch(int[] arr,int target){
            int left = 0;
            int right = arr.length-1;
            while (left<=right){
                int mid = (left+right)/2;
                if (arr[mid]==target){
                    return mid;
                }else if (arr[mid]<target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            return -1;
        }
    }
    
    

    如果想看Java实现二分查找算法(采用递归方式)的代码请查看之前文章,点击前往【Java实现二分查找算法(递归)

    更多相关内容
  • 主要介绍了Java实现二分查找算法,实例分析了二分查找算法的原理与相关实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • Java实现二分查找算法

    千次阅读 2020-04-20 00:00:00
    欢迎点击「算法与编程之美」↑关注我们!本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。前言不知道大家玩过这么一个游戏没---猜数字大小。先在心...

    前言

    不知道大家玩过这么一个游戏没---猜数字大小。先在心里想一个100以内的数字,然后参与者来猜数字,每次只提示大了或者小了,直到参与者猜中心中所想的数为止。

    怎么来快速猜出来呢?利用二分法查找就可以快速实现。接下来给大家讲解二分法查找的思想,以及如何用java代码实现。

    算法思想

    二分法查找又称为折半查找,二分法查找的基本思想是把数组中的元素从小到大有序地存放进数组中,首先将给定值与数组中间位置的值作比较,如果相等,则匹配成功。否则,若比较值小了,则在数组的前半部分继续二分法查找;若比较值大了,则在数组后半部分进行二分法查找。如此循环往复,直到比较值与中间值匹配,完成查找。

    流程图:

      Java代码实现:

    public class test {
         public static void main(String[]  args) {
     //    

    展开全文
  • Java 二分查找 算法

    2014-07-04 10:38:46
    Java 二分查找算法的示例代码。 欢迎访问个人博客。 http://blog.csdn.net/evanwang1987
  • (一) 实现原理:二分査找就是折半查找,其基本思想是:是在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于...

           (一)  实现原理:二分査找就是折半查找,其基本思想是:是在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组 为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半,时间复杂度为Ο(logn) 。

         (二)实现方式:我采用递归和顺序的方式实现,接下来直接上代码:
        
        //二分查找递归实现
        public static int binarySearch(int[] arr,int low,int high,int key ) {
            int mid = (low + high)/2;
            if(arr[mid] == key) {
                index = mid;
                return mid;
            }
            if(low>high) {
                return -1;
            }else if(key > arr[mid]) {
                return binarySearch(arr,mid+1,high,key);
            }else if(key < arr[mid]) {
                return binarySearch(arr,low,mid-1,key);
            }
            return -1;
                
        }
        
        //二分顺序查找实现
        public static int binarySearch(int[] arr,int key ) {
            int high = arr.length;
            int low  = 0;
            while(low <= high) {
                int mid = (low + high)/2;
                if(key == arr[mid]) {
                    return mid;
                }else if(key > arr[mid]){
                    low  = mid + 1;
                }else if(key < arr[mid]){
                    high = mid - 1;
                }
            }
            return -1;
        }

    (三)测试

        public static void main(String[] args) {
            int[] array = {1,2,3,4,5,6,7,8,9,10};
            System.out.println("递归:所查询值的下标值为:"+binarySearch(array,0,array.length-1,7));
            System.out.println("顺序:所查询值的下标值为:"+binarySearch(array,6));
        }

     

    展开全文
  • 主要介绍了Java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • java实现二分查找

    千次阅读 2021-05-28 11:31:48
    Java实现数组二分查找 给定一个有序的int数组,指定查找元素,要求查找该元素在给定数组中的位置。 假定给定数组为:[1, 3, 5, 7, 9, 11, 13, 15]。 思路分析 所谓二分查找,就是每次查找都取查找范围二分之一处...

    Java实现数组二分查找

    给定一个有序的int数组,指定查找元素,要求查找该元素在给定数组中的位置。
    假定给定数组为:[1, 3, 5, 7, 9, 11, 13, 15]。

    思路分析

    所谓二分查找,就是每次查找都取查找范围二分之一处的元素与目标值进行比较。

    • 已知给定数组为有序的,那么我们每次截取数组的中间元素与查找元素进行比较。
    • 如果中间元素小于给定元素,则下一次我们将查找范围缩小到中间元素的右侧再次比较;
    • 否则,我们将下一次查找范围缩小至中间元素的左侧再次进行比较;
    • 以此类推,当我们查找范围的左侧位置和右侧位置重合的时候,表示查找结束了;
    • 此时我们将最后一次查找范围左侧的元素与给定目标元素值进行比较
      • 如果相等则表示在给定数组中找到了目标元素,直接返回对应的索引
      • 否则表示找到目标元素返回-1。

    上图分析

    要查找的元素每次都向左移的情况:

    在这里插入图片描述

    要查找的元素每次比较都向右移的情况:

    在这里插入图片描述

    要查找的元素同时存在左移与右移的情况:

    在这里插入图片描述

    代码实现

    根据示意图写出代码:

    /**
     *  两边向中间靠的方式,每次取中间值与目标值进行比较,
     *   如果中间值小于目标值,则将比较范围右移,否则将比较范围左移
     *   当左侧索引不小于右侧索引时查找结束,将左侧索引与目标值比较,相等则表示找到目标值返回所在索引,否则表示没有找到返回-1
     */
    public static int binarySearch2(int[] nums, int target) {
        if (null == nums || nums.length == 0) { return -1; }
    
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
    

    测试效果:

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • Java实现二分查找算法(折半查找)

    千次阅读 2020-03-28 11:18:44
    代码实现与过程分析 import java.util.Arrays;... * 标题:Java实现二分查找算法(折半查找) * 作者:Nstar * 时间:2020年3月27日 */ public class Test28{ public static void main(String[] args)...
  • Java实现二分查找

    千次阅读 2021-03-23 13:35:53
    本教程将介绍Java中的进制搜索和递归进制搜索,以及其算法实现Java Binary Seach代码示例: Java中的进制搜索是一种用于在集合中搜索目标值或键的技术。它是一种使用“分而治之”技术搜索密钥的技术。 ...
  • java实现二分查找算法,两种方式实现,非递归和递归 java基础算法 概念:二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按...
  • Java二分查找递归算法

    2017-10-12 01:02:23
    Java二分查找递归算法
  • 主要介绍了Java实现的两种常见简单查找算法,结合具体实例形式分析了java快速查找与二分查找的原理与简单实现技巧,需要的朋友可以参考下
  • 二分查找算法Java实现

    万次阅读 2018-07-17 10:31:12
    ①适用于经常查找的、但是不变的(增删)的有序...//注意:二分查找必须用在有序列表中进行二分查找 public class BinaryChopTest {  public static void main(String[] args) { int[] arrays = {1, 6, 10, 11, 12...
  • 主要介绍了java算法二分查找法的实例详解的相关资料,这里提供简单实例帮助大家学习理解这部分内容,需要的朋友可以参考下
  • java实现折半查找算法

    2019-12-06 17:27:55
    所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找
  • 实现思路: (1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。 (2)如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复...
  • java通过实际代码演示,及对代码讲解,解释二分查找的逻辑。
  • java实现二分查找算法

    千次阅读 2013-01-16 22:40:42
    欢迎关注技术公众号 import java.util.Scanner;...* 功能:对非重复有序元素集合实现二分查找(折半查找) */ public static void main(String[] args) { BinaryFind bf = new BinaryFind(); System.out.pr...
  • 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 要求: 必须采用顺序存储结构。 必须按关键字大小有序排列。...
  • 二分查找算法java实现

    千次阅读 2021-06-28 18:08:25
    文章目录前言一、二分查找思路二、代码实现1.递归实现2.非递归实现总结 前言 提示:以下是本篇文章正文内容,仅供参考 一、二分查找思路 二分查找只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后...
  • 主要介绍了java 算法二分查找与折半查找的相关资料,需要的朋友可以参考下
  • Java递归实现二分查找算法 二分查找即在一个排好序的数列中查找指定的数,把一个数列分成两部分,对中间的数与要查找的数比较,如果相等就退出算法得到该数的下标,如果大于要比较的数就往前移继续分成两半再比较,...
  • 二、二分查找Java实现 public class BinarySearch { public static void main(String[] args) { int[] arrays = new int[]{1,2,3,4,6,6,7,7,8,9,10}; int target = 7; System.out.println(search(arrays...
  • 本文详细介绍了JAVA冒泡排序和二分查找实现,虽然这两种算法比较简单,但是确实我们必须需要掌握的。下面来看看。
  • 本文解释基于线性结构的二分查找算法,并给出几种实现的代码示例。 需求场景 假设电商系统中,每天大量用户访问产品页面,用户可以设置低于一定价格的条件过滤产品,并从过滤结果中选择商品加入购物车。因每秒同时...
  • java实现二分查找,分别采用递归方式,非递归方式实现
  • 本篇文章主要介绍了详解Java数据结构和算法(有序数组和二分查找),具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Java编程:二分查找算法实现代码

    千次阅读 2020-02-06 16:59:15
    二分查找算法 又叫折半查找,要求待查找的序列有序。每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小, 则在后半部分循环这...
  • 折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程从数组的中间元素开始,如果中间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 118,510
精华内容 47,404
关键字:

java实现二分查找算法

java 订阅