精华内容
下载资源
问答
  • 2022-01-11 09:05:46

    二分查找

    1、前提:序列必须是有序的。

    2、实现思想:

    (1)定义low指针指向第一个元素,下标索引为0,定义high指针指向最后一个元素,下标索引为length-1,定义mid指针指向(low+high)/2.

    (2)若目标元素>mid所对应的元素值,则high不变,low=mid+1

    若目标元素<mid所对应的元素值,则low不变,high=mid-1

    (3)重复第二个步骤,注意low不可能大于high,如果该元素存在,最终有low=high=mid,反之则元素不存在

    import java.util.Scanner;
    
    public class BinarySearch {
        public static void main(String[] args) {
            //使用二分查找元素并输出索引下标
            int[] arr = {11, 25, 32, 45, 65, 88, 99};
            Scanner sc  = new Scanner(System.in);
            System.out.println("请输入一个数:");
    
            int number = sc.nextInt();
            int low = 0;
            int high = arr.length - 1;
            int mid;
            boolean flag = true;
    
            while (low <= high) {
                mid = (low + high) / 2;   //取中间位置
                int midValue = arr[mid];
                if (midValue == number) {
                    System.out.println("找到了元素" + number + ",下标索引为:" + mid);   //查找成功则返回所在位置
                    flag = false;
                    break;
    
                } else if (midValue > number) {
                    high = mid - 1;  //从前半部分继续查找
                } else {
                    low = mid + 1;  //从后半部分继续查找
                }
            }
            if (flag) {
                System.out.println("没有此元素,查找失败");  //查找失败
            }
        }
    }

    更多相关内容
  • java实现折半查找算法

    2019-12-06 17:27:55
    所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找
  • 算法前提 1、必须采用顺序存储结构。 2、必须按照关键字大小有序排列。 算法思想 ...代码 public class BinSrch { public static void main(String[] args) { int[] arr = {6,12,15,18,22,25,28,3

    算法前提

    1、必须采用顺序存储结构。
    2、必须按照关键字大小有序排列。

    算法思想

    先将数组中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。

    代码

    public class BinSrch {
        public static void main(String[] args) {
            int[] arr = {6,12,15,18,22,25,28,35,46,58,60};
            int result1 = BinSerch(arr, 12);
            int result2 = BinSerch(arr, 58);
            int result3 = BinSerch(arr, 50);
            System.out.println(result1);
            System.out.println(result2);
            System.out.println(result3);
        }
    
        //在有序表中折半查找关键字等于k的元素,若找到,则函数值为该元素在数组中的位置,否则返回-1
        public static int BinSerch(int[] arr,int k){
            int low = 0; //数组最左边的下标
            int high = arr.length-1; 数组最右边的下标
    
            while (low <= high){
                int mid = (low + high) / 2;
    
                if (k == arr[mid]){ // 找到带查找的元素
                    return mid;
                }else if (k<arr[mid]){ // 未找到,则继续在前半区间进行查找
                    high = mid -1;
                }else {   // 未找到,则继续在后半区间进行查找
                    low = mid + 1;
                }
            }
            // 都没找到则返回一个默认值-1
            return -1;
        }
    }
    

    输出结果

    在这里插入图片描述

    展开全文
  • JAVA 数据结构二分法查找代码。(实验)
  • 折半查找代码

    2015-06-14 17:09:52
    折半查找是一种数据结构算法 非常有用 我们用C语言实现了查找 简单有效
  • java折半查找

    2022-01-10 21:33:38
    java折半查找

    折半查找操作:使用折半查找有序数组中元素。找到返回索引(在数组中的位置),不存在输出-1。
    分析:折半查找的前提是数组有序。
    假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.
    可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.  
    (1)开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为mid>x,故应在前半段中查找。
    (2)令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>mid,故确定应在后半段中查找。
    (3)令新的front=mid+1=2,而end=2不变,则新mid=2,此时a[mid]=x,查找成功。
    (4)如要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。

    import java.util.Scanner;
    public class SuZu4 {
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int[] a = {3, 12, 24, 36, 55, 68, 75, 88};
            System.out.print("请输入要查找的数:");
            int n =sc.nextInt();
    
            int front = 0;
            int end = a.length - 1;
            int mid = (front + end) / 2;
            do {
                int jg;
                if (a[mid] > n) {
                    end = mid - 1;
                    mid = (front + end) / 2;
                    if (end < front) {
                        System.out.println("查找不成功");
                        return;
                    }
                } else if (n > a[mid]) {
                    front = mid + 1;
                    mid = (front + end) / 2;
                    if (front > end) {
                        System.out.println("查找不成功");
                        return;
                    }
                }
            } while (a[mid] != n);
            System.out.println(mid);
        }
    }

     折半查找递归操作

    
    import java.util.Scanner;
    
    public class SuZu62 {
        public static void main(String[] args) {
            int[] a = {3, 12, 24, 36, 55, 68, 75, 88};
            Scanner sc = new Scanner(System.in);
            System.out.print("请输入要查找的数:");
            int n = sc.nextInt();
            int s = seek(a, 0, a.length - 1, n);
            System.out.println(s);
    
        }
    
        public static int seek(int[] arr, int front, int end, int n) {
            int mid = (end + front) / 2;
            if (front <= end) {
                if (arr[mid] == n) {
                    return mid;
                } else if (arr[mid] > n) {
                    return seek(arr, front, mid - 1, n);
                } else {
                    return seek(arr, mid + 1, end, n);
                }
            } else {
                return -1;
            }
        }
    }

    结果如上

    展开全文
  • java实现折半查找

    2021-02-12 14:35:04
    } } O(1):直接寻址到 O(n):遍历n个元素 O(logn):随着元素增加,呈现指数关系 O(n2):增加一倍元素,时间增加4倍 折半查找的算法时间复杂度最好的情况是O(1),平均情况下是logn。 分析一下,折半查找的...

    package althorgrim;

    /**

    * 1、必须采用顺序存储结果

    * 2、关键字必须有序

    * @author hanrk-2734

    *

    */

    public class TestBinarySearch {

    public static int binarySearch(int a[],int goal){

    int high=a.length-1;

    int low=0;

    while (low<=high) {

    int middle=(low+high)/2;

    if (a[middle]==goal) {

    return middle;

    }

    else if (a[middle]>goal) {

    high=middle-1;

    }

    else {

    low=middle+1;

    }

    }

    return -1;

    }

    /**

    * @param args

    */

    public static void main(String[] args) {

    // TODO Auto-generated method stub

    int[] src = new int[] {1, 3, 5, 7, 8, 9};

    System.out.println(binarySearch(src, 3));

    }

    }

    O(1):直接寻址到

    O(n):遍历n个元素

    O(logn):随着元素增加,呈现指数关系

    O(n2):增加一倍元素,时间增加4倍

    折半查找的算法时间复杂度最好的情况是O(1),平均情况下是logn。

    分析一下,折半查找的算法时间复杂度为什么是logn?

    算法的时间复杂度取决于运算时间,折半查询中主要依赖while循环次数,那么while循环次数是多少?假设有16个元素的数组进行折半查询,查询元素13

    如果是n个元素,那么就是:

    可以得出 k=logn

    public class Demo {

    public static void main(String[] args) {

    int[] array = new int[] {3,6,8,9,10,11,13,19,25};

    //声明角标 最小 和 最大 角标 和折半角标

    int min=0;

    int max=array.length-1;

    int mid=(max+min)/2;

    //声明要查找的值

    int key=13;

    //循环查找 循环里肯定要折半的操作

    //我现在已经 明确知道 循环什么时候停止

    //使用 key 和 中间角标的值 比较 如果相等 循环停止

    while(key!=array[mid]) {

    if(key>array[mid]) {

    min=mid+1;

    }else if(key

    max=mid-1;

    }

    //重复折半的操作

    mid=(max+min)/2;

    //如果数组中没有这个数 会造成死循环

    //需要一个出口让程序停止

    if(min>max) {

    //这里说明 没找到这个数 需要停止循环

    mid=-1;

    break;

    }

    }System.out.println("坐标是:"+mid);

    }

    }

    展开全文
  • 折半查找法.java

    2021-09-14 12:26:56
    哈喽,很高兴见到大家,这次是用java语言写的折半查找法,实际上, 小白通过对比C语言里的二分法,小白发现,这两种办法的原理相同。 可以参考高中学的查找零点的办法。 import java.util.Scanner; public class ...
  • 第1关:折半查找(二分查找) 本关任务:给定一个排好序的数组,然后输入另一个整数,判断该整数在数组中的什么位置,返回该整数第一次出现的位置(位置从0开始),否则返回-1。 package step1; public class Task ...
  • 二分查找又称折半查找,优点是比较的次数少,查找速度快,但是要求待查找的序列是有序的。升序的数据集合,先找出升序集合中最中间的元素,将数据集合划分为两个子集,将最中间的元素和关键字key进行比较,,如果...
  • 折半查找介绍:折半查找,找的是一个有序列表。理论就是先找中间的,如果中间数大于大于目标数,那么就只需要找上半份数据中再折半查找就可以了。一直到找到为止,不用遍历所有数据,效率很高。实现折半查找的方法...
  • Java实现折半查找

    千次阅读 2018-03-30 20:15:21
    折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。 但是,折半查找的先决条件是查找表中的数据元素必须有序。 以下是折半查找的实现 public class SearchUtils { public static void main...
  • 折半查找算法

    2021-04-17 11:04:42
    6.折半查找 请点评如果不是从一组随机的序列里查找,而是从一组排好序的序列里找出某个元素的位置,则可以有更快的算法:例11.4.折半查找#include #define LEN 8int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };int binary...
  • Java算法之折半查找

    千次阅读 2020-04-26 10:43:49
    Java 算法之折半查找法 算法介绍 折半查找法要求线性表是有序的,即表中记录按关键字有序(假设是递增有序的)。 折半查找的基本思路:设 R[low, ···, high] 是当前的查找区间,首先确定该区间的中间位置 mid = ...
  • 递归调用的折半查找java代码,算法分析与设计实验报告。
  • 主要介绍了Java数据结构实现折半查找的算法过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 下面的代码中展示有简单查找法和二分查找法(也叫折半查找法),将进行依次分析。 /* 需求:查找某个元素在数组中的位置 思路: 遍历数组中的每个元素与所要查找的元素进行比较,相同时返回其索引值 步骤: 1.定义...
  • import java.util.Comparator;public class MyUtil {public static > int binarySearch(T[] x, T key) {return binarySearch(x, 0, x.length- 1, key);}// 使用循环实现的二分查找public static int binarySearch...
  • // 顺序折半查找下标 public static int BinarySearch(int key, int[] num_list) { int smaller = 0; int bigger = num_list.length - 1; while(smaller <= bigger){ int mid = smaller + (bigger -...
  • 顺序查找和折半查找代码实现)

    千次阅读 多人点赞 2020-12-09 22:10:16
    直接上代码 //顺序查找算法 int Search(Table table , int key){ table.elem[0] = key; int i; for(i = table.length-1;table.elem[i] != key;--i); return i; } 下面是顺序查找的优化算法(基于顺序表的顺序...
  • // 折半查找 public static void main(String[] args) { int[] arr = {2,6,3,1,8,9,10}; int index = binarySearch(arr,8); System.out.print(index);//输出 4 } /** * * @param arr 要进行查找的数组...
  • java实现折半查找代码如下: package com; import java.util.Scanner; public class binarySearch{ public static void main(String[] args) { int arr[]={11,23,26,30,36}; System.out.println("请...
  • 下面是具体代码:(本人懒,没写注释,不过仔细看代码,还是很简单的) #include… 第一步:输入15个整数 第二步:对这15个数进行排序 第三部:输入一个数,在后在排好序的数中进行折半查找,判断该数的位置 实现代码如下: ...
  • java折半查找算法

    2021-04-17 02:47:29
    high 时表示查找区间为空,查找失败 } Java 代码: /** * 二分查找算法 * * @param srcArray 有序数组 * @param target 被查找的元素 * @retur......6 、不断利用循环和折半查找算法查找一个整数 n 是否在一个无序的 ...
  • 一、顺序查找************* 二、折半查找************* 三、输出样例*************
  • 带有哨兵的顺序表查找和二分法查找(折半查找)(java代码+说明 一:带有哨兵的顺序表查找 1、算法设计: * 在一个线性表中,按照从前往后或者从后往前的顺序依次查找,如果查找到关键字和给定值相等,则返回...
  • 算法复杂度:二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果xa[n/2],则只要在数组a的右半部搜索x.时间复杂度无非就是while循环的次数!总共有n个元素...
  • 折半查找Java语言描述

    2020-07-19 16:07:28
    折半查找的先决条件是查找表中的数据元素必须有序。 代码 public int binarySearch(Comparable[] a,Comparable findElem) { int low=0; int high=a.length()-1; int mid; while(low<=high) {
  • 二分查找又称折半查找,优点是比较次数少,查找速度快;其缺点是要求待查表为有序表,且...该算法时间复杂度最坏为:O(logn)注意点有mid、low、high其Java实现代码如下:public class BinarySearch {/*** @param ...
  • java基础-数组的折半查找原理作者:尹正杰版权声明:原创作品,谢绝转载!否则将追究法律责任。如果让你写一个数组的查找功能,需求如下:在一个数组中,找一个元素,是否存在于数组中, 如果存在就返回这个元素,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,067
精华内容 3,626
关键字:

折半查找java代码

java 订阅