精华内容
下载资源
问答
  • Java 数组二分查找
    2021-08-03 15:40:23

    想在数组中找到某个元素的索引位置,从头遍历数组匹配,数组数据少的时候可以,但是数组数据大的时候就会变慢,耗费性能,这时就需要二分查找法

    比如:

    从1 - 10 之间,判断8 的索引位置

    首先求中间索引号,0 - 9 ==》(0+9)/ 2 = 4,则中间索引的数值为 5

    判断 8 与中间数值的大小关系

    8  > 5,则8位于5 - 10 之间

    8 < 5,则8位于1 - 5 之间

    8 = 5,则就是我们找的索引

        public static void main(String[] args) {
            int[] arr = new int[10];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = i;
            }
            int a = 7;
            int low = 0;
            int high = arr.length -1;
            while(low < high) {
                int mid = (low + high) / 2;
                if (arr[mid] > a) {
                    high = mid;
                } else if (arr[mid] < a) {
                    low =mid;
                } else {
                    System.out.println(mid);
                    break;
                }
            }
        }

    总之意思就是:

    查找的值大于中间值,则  最小索引 = 中间索引

    查找的值小于中间值,则  最大索引 = 中间索引

    更多相关内容
  • java数组二分查找

    2015-11-02 16:56:58
    Java数组二分查找代码,将给定数组排序,然后接收键盘键入的整形数字,并查找该数字。
  • 首先二分查找是一个具有前提的算法,前提就是必须这个数组是有序的,如果你是无序的要么你使用别的算法或者你排好序了再用.(提一嘴有些人叫他折半查找都是一样的) 思路:既然是二分查找首先我们先确定中间值,因为一半...

    首先二分查找是一个具有前提的算法,前提就是必须这个数组是有序的,如果你是无序的要么你使用别的算法或者你排好序了再用.(提一嘴有些人叫他折半查找都是一样的)

    思路:既然是二分查找首先我们先确定中间值,因为一半儿一半儿嘛(要不然咋叫二分查找), 中间值 = (开始元素的下标 + 结束元素的下标)/2

    这时候把你输入的元素和这个中间值比较,如果大那就在右半部分,反之亦然.当然如果你输入要查找的值刚好在中间,恭喜,幸运儿诞生了

    这里我是直接封装了一个方法

    import java.util.Arrays;
    import java.util.Scanner;
    
    public class ArrayUtilsFound {
       public static int[] HalfFound(int[] array){
          Arrays.sort(array);
          Scanner scan = new Scanner(System.in);
          int begin = 0;
          int end = array.length - 1;
          int middle = 0;
          int num = scan.nextInt();
    
          boolean flag = false;
          while(begin <= end){
             middle = (begin + end)/2;
             if (array[middle] == num) {
                flag = true;
                break;
             } else if (array[middle] > num) {
                end = middle - 1;
                //-- 这里是中间值比你输入的大,在左边,所以要中间的元素-1,因为你中间的元素已经比较过了
             } else {
                begin = middle + 1;
                //-- 中间值比输入的值小,在右边,所以要+1因为要在右边进行二分查找,而中间值不参与
             }
          }
          if (flag) {
             System.out.println("中间的值为:\t" + middle);
             
          } else {
             System.out.println("不存在");
          }
    
          scan.close();
          return array;
       }
    }
    

    展开全文
  • JAVA数组二分查找

    2019-02-27 22:16:01
    JAVA数组二分查找前言查找原理代码实现 前言 二分查找是一种比较高效的查找方式,使用此查找方式需要先将数组进行排序,如果数组未经排序效率就会很低,所以数组是必须要经过排序的。 查找原理 Created with Raphaë...

    JAVA数组二分查找

    前言

    二分查找是一种比较高效的查找方式,使用此查找方式需要先将数组进行排序,如果数组未经排序效率就会很低,所以数组是必须要经过排序的

    查找原理

    Created with Raphaël 2.2.0 排序后数组 计算数组中间值 判断数组中间值是否 等于我们要查找的元素 是我们查找的元素返回当前middle下标 结束 判断当前中间下标是否已经为0 返回-1代表未找到此元素 判断当前中间元素是否 大于我们要查找的元素 如果不大于那说明我们 要找的元素在中间值 的右边(数组从小到大排序), 那么递归将之前的数组的start 换为中间值。 如果不大于那说明我们 要找的元素在中间值 的左边(数组从小到大排序), 那么递归将之前的数组的end 换为中间值。 yes no yes no yes no

    代码实现

    @Test
        public void test1() {
            Integer[] arr = new Integer[]{4, 3, 2, 1, 5, 10, 1, 11, 1, 1, 2, 123, 42142, 1};
            arr = mergeSort(arr, Comparator.naturalOrder()); //使用二分法需要先将数组排序 (归并排序)
    
            for (Integer integer : arr) {
                System.out.println(integer);
            }
    
            System.out.println(binarySearch(arr, 42142, 0, arr.length, Comparator.naturalOrder()));
        }
    
        /**
         * 使用二分法查找元素,如果有多个仅仅只返回其中一个数组下标(乱序)。
         *
         * @param arr 目标数组
         * @param find 查找元素
         * @param start 数组开始下标
         * @param end 数组结束下标
         * @param comparator 元素比较规则
         * @return 查找的元素在目标数组的下标
         */
        private int binarySearch(Object[] arr, Object find, int start, int end, Comparator comparator) {
            if (arr == null) throw new NullPointerException("arr can not be empty!");
    
            int middle = (end - start) / 2 + start;
    
            int result = comparator.compare(arr[middle],find);
    
            if(middle == 0 && result != 0) return -1;
    
            if(result > 0) {
                return binarySearch(arr, find, start, middle, comparator);
            } else if(result < 0) {
                return binarySearch(arr, find, middle, end, comparator);
            } else {
                return middle;
            }
        }
    
        /**
         * 归并排序
         *
         * @param arr 排序数组
         * @param comparator 比较规则
         * @return 排序后的数组
         */
        private <T> T[] mergeSort(T[] arr, Comparator<T> comparator) {
            T[] cache = arr.clone();
            int step = 2;
    
            while (step <= arr.length * 2) {
                int c = 0;
                for (int i = 0; i < arr.length; i += step) {
                    int l = i, r = l + (step >> 1) > arr.length ? arr.length : i + (step >> 1);
                    int lm = r;
                    int rm = i + step > arr.length ? arr.length : i + step;
    
                    while (l < lm && r < rm) {
                        if (comparator.compare(arr[l],arr[r]) > 0) {
                            cache[c] = arr[r];
                            r++;
                            c++;
                        } else {
                            cache[c] = arr[l];
                            l++;
                            c++;
                        }
                    }
                    while (l < lm) {
                        cache[c] = arr[l];
                        l++;
                        c++;
                    }
                    while (r < rm) {
                        cache[c] = arr[r];
                        r++;
                        c++;
                    }
                    System.arraycopy(cache, 0, arr, 0, cache.length);
                }
                step = step << 1;
            }
    
            return (T[]) cache;
        }
    

    归并排序可以参考 > 归并排序

    展开全文
  • JAVA数组——二分查找

    2022-01-19 16:32:27
    主题:二分查找 前提:数组必须是有序的数组(通过Arrays.sort(要排序的数组)) 方法一:二分查找常规方法 mid为left和right的中间值。当要查找的数在mid左边,right值为mid-1;当要查找的数在mid右边时,left的值...

    主题:二分查找 前提:数组必须是有序的数组(通过Arrays.sort(要排序的数组))

    方法一:二分查找常规方法
    mid为left和right的中间值。当要查找的数在mid左边,right值为mid-1;当要查找的数在mid右边时,left的值为mid+1。若要找的值不存在,则返回-1.
    在这里插入图片描述
    代码:

    public static int binarySearch(int[]array,int key){
            int left=0,right=array.length-1;
            while(left<=right){
                int mid=(right+left)/2;
                if(array[mid]<key){
                    left=mid+1;
                }
                else if(array[mid]>key){
                    right=mid-1;
                }
                else if(array[mid]==key){
                    return mid;
                }
            }
            return -1;/*如果没有找到返回 -1*/
        }
        public static void main(String[] args) {
            int[] array={11,48,98,99,3,9};
            Arrays.sort(array);/*系统自带数组排序*/
            int ret=binarySearch(array,9);
            System.out.println(ret);
        }
    

    方法二:使用Arrays.binarySearch(int[] a, int key)
    int[] a:需要要查找的数组
    int key:需要找的数
    代码:

     public static void main(String[] args) {
            int[] array={11,48,98,99,3,9};
            Arrays.sort(array);/*系统自带数组排序*/
            int ret=Arrays.binarySearch(array,9);
            System.out.println(ret);
        }
    
    展开全文
  • 数组——简单二分查找 二分查找:也叫折半查找( Binary Search ), 假设表中元素是按升序排列,将表中间位置记录的数与查找数比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果...
  • Java数组二分查找

    2019-10-30 18:56:16
    但是二分查找有一个前提就是数组必须有序。 二分查找的思想 首先假设数组元素呈升序排列,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止;如果x<a[n/2],则我们...
  • java数组二分查找

    2016-07-06 19:03:58
    1.新建HalfFind类,在main方法中,调用二分查找法。public class HalfFind { public static void main(String[] args) { int[] a = { 1,2,3,4,5,6,7, 8, 9 }; //折半查找对于数组的是有序数列 System.out.println...
  • public class 数组查找算法1 { public static void main(String[] args) { //目标数组 int[] arr = new int[] {2,3,4,5,6,8,4,7,0}; //目标元素 int target = 8; //目标元素所在的下标 int ...
  • java代码-数组二分查找
  • java-数组二分查找

    千次阅读 2018-08-13 21:17:37
    * 数组高级二分查找代码 * B:注意事项 * 如果数组无序,就不能使用二分查找。 * 因为如果你排序了,但是你排序的时候已经改变了我最原始的元素索引。 */ public static void main(Strin...
  • 1、二分查找:前提数组元素必须有序 2、 二分查找的思想: 每一次都查中间索引的那个元素,比较大小就能减少一半的元素。 3、注意:二分查找不是找该元素第一次出现的索引。 比如下面这个数组,找4元素的索引,找...
  • 数组中的查找

    2019-08-06 12:44:48
    二维数组中的查找,逐行扫描,行内使用二分查找。最差情况需要扫描所有行,待完善
  • 2.二分查找(要求数组有序); 3.插值查找; 4.斐波那契查找 本文使用递归思想带来二分查找及其优化 二分查找思路分析 1.首选确定该数组中间下标mid=(left+right)/2; 2.然后让需要查找的数findVal与arr[mid]...
  • 本篇文章主要介绍了详解Java数据结构和算法(有序数组二分查找),具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 使用这个方法之前我们需要注意:二分查找法只针对于有序数组。 首先定义一个简单的一维数组:int []a ={1,2,3,4,5,6,7,8,9}; 解释一下何为二分法:三点两段,我们将数组的起始点,终点,以及中间点作为三点,将整个...
  • public class ... * 用 Java 代码实现了一个最简单的二分查找算法 * @param a 已经排序的数组 * @param n 数组大小 * @param value 待查找的值 * @return */ public static int bsearch(int[] a, in
  • java 二分查找查找到数组中指定元素

    千次阅读 2019-11-19 18:01:04
    java 实现二分查找 查找有序数组中的某一元素 话不多说,直接上代码 /** * @param arr 传递数组 * @param key 查找的值 * @return 返回值的索引 */ public static int test(int [] arr,int key){ int low = 0;...
  • 学习Java二分查找

    2020-12-12 16:08:32
    二分查找法,只能查找按顺序排列的数组(升序,降序)。 查找原理 1、将数组中间位置的数据与查找数据比较,如果两者相等,则查找成功; 2、否则利用中间位置记录将数组分成前、后两个子数组; 3、如果中间位置数据...
  • 数组 数组的定义 数组是相同类型数据的有序集合,数组描述的是相同类型...数组本身就是对象,Java中对象是在堆中的,因此数组无论保存原始类型还是其他对象类型,数组对象本身是在堆中存储的。 数组声明 在声明数组变量
  • 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 又例如{...
  • 折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组查找某一特定元素的搜索算法。 搜索过程从数组的中间元素开始,如果中间...
  • 二分查找——有序数组

    千次阅读 2022-04-10 12:19:21
    二分查找算法的详解
  • 数组二分查找

    2019-05-23 19:01:03
    数组二分查找(根据元素) 代码详解 package arrays; /** 数组二分查找 条件:数组元素不能重复且有序 结果:有则返回下标元素 无则返回-1 */ public class ArrayBinarySearch { ...
  • Java递归方法实现二分查找法 1.二分查找输入查找值,返回查找值的数组下标(查找的数组arr,数组的开头start,数组的结尾end,查找的值key) 先判断输入的start(开头)是否比end(结尾)大,如果比end(结尾)大...
  • 请实现有重复数字的升序数组二分查找 给定一个 元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的第一个出现的target,如果目标值存在返回下标,否则返回 -1 示例1 输入: [1,2,4,...
  • 今天博主分享两个查找数组中指定元素的算法:顺序查找与二分查找 小小目录1.顺序查找2. 二分查找 1.顺序查找 给定一个数组, 再给定一个元素, 找出该元素在数组中的位置. 代码如下: //顺序查找 public static ...
  • java数组中如何查找元素的位置?

    千次阅读 2021-02-12 13:52:20
    就拿我们最近学习的java数组中,想要对元素查找可以选择binarySearch的方法,不过这个用法必须要先对数组进行排序。接下来就java中使用binarySearch查找元素的方法带来详解。1、binarySearch概念binarySearch()方法...
  • 题目:请实现有重复数字的升序数组二分查找 给定一个 元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的第一个出现的target,如果目标值存在返回下标,否则返回 -1 思路:和普通...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 130,066
精华内容 52,026
关键字:

java数组二分查找

java 订阅