精华内容
下载资源
问答
  • 2019-03-09 17:07:08

    首先,Java的折半查找法适用于有序数组中某一元素下标的查找。例如:

    
    //折半查找
    public class halfSerach {
    	public static void main(String[] args) {
    		int[] a = {12,23,34,36,47,108};
    		int index = getIndex(a,12);
    		System.out.println("index="+index);
    		
    	}
    	
    	public static int getIndex(int[] a,int key) {
    		int min,max,mid;
    		min=0;
    		max=a.length-1;
    		
    		while(min<max) {
    			mid=(min+max)/2;
    			if(a[mid]<key) 
    				min=mid+1;
    			else if (a[mid]>key) {
    				max=mid-1;
    			}
    			else {
    				return mid;
    			}	
    		}
    		return -1;
    		
    	}
    	
    
    }

    除了上诉一种方法,Java中还封装了一种方法

    int index = Arrays.binarySearch(a, 34);

    可用此函数直接找到数组中元素34的下标,与第一种方法结果相同。

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

    2019-12-06 17:27:55
    所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找
  • JAVA实现折半查找算法

    2020-07-16 11:01:13
    JAVA实现折半查找算法 package demo; import java.util.Scanner; public class wdnmd2 { public static void main(String[] args) { int[] arr = {10, 20, 30, 40, 50, 60}; Scanner sc = new Scanner(System....

    JAVA实现折半查找算法

    package demo;
    
    import java.util.Scanner;
    
    public class wdnmd2 {
        public static void main(String[] args) {
            int[] arr = {10, 20, 30, 40, 50, 60};
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入一个数");
            int n = sc.nextInt();
            int s = select(arr, n);
            if (s > 0) {
                System.out.println("找到了" + n);
            } else System.out.println("没找到" + n);
        }
    
        public static int select(int[] arr, int n) {
            int minindex = 0;
            int maxindex = arr.length - 1;
            int midindex;
            while (minindex <= maxindex) {
                midindex = (minindex + maxindex) / 2;
                if (n > arr[midindex]) {
                    minindex = midindex + 1;
                } else if (n < arr[midindex]) {
                    maxindex = midindex - 1;
                } else if (n == arr[midindex]) {
                    return arr[midindex];
                }
            }
            return -1;
        }
    
    }
    

    运算结果:在这里插入图片描述

    解析:折半查找算法的前提是排序后的数组,每次拿查找元素和中间元素去比较,然后改变索引**

    第一种情况:查找元素==中间索引所对应的元素,则查找成功

    第二种情况:查找元素<中间索引所对应的元素,则要改变最大索引,maxindex=midindex-1;

    第三种情况:查找元素>中间索引所对应的元素,则要改变最小索引,minindex=midindex+1;

    展开全文
  • // 折半查找 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 要进行查找的数组...

         折半查找

    1. 首先用要查找的关键字值(key)与中间位置结点的关键字值(arr[mid])相比较;
    2. 若比较结果相等,则查找完成;若不相等,再根据要查找的关键字值(key)与该中结点关键值(mid)的大小来确定下一步在那个子表中进行;
    3. 若待查关键值大于中间结点的关键字值(key > arr[mid])),则应查找中间结点以后的字表,否则(key < arr[mid])),查找中间结点以前的字表;
    4. 重复步骤1~3,直到找到满足条件的结点,或者明确表中没有这样的结点。
    5. 图解:

     

        //折半查找
        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 要进行查找的数组,要求数组必须是有序的
         * @param key 要查找的元素
         * @return 返回要查找的元素在数组的索引位置, 返回-1表示没找到
         */
        public static int binarySearch(int[] arr,int key){
            int low = 0;
            int high = arr.length - 1;
            int mid;
            while (low <= high) {
                mid = (low + high) / 2;
                if (key < arr[mid]) {
                    high = mid - 1;
                }
                if (key > arr[mid]) {
                    low = mid + 1;
                }
                if (arr[mid] == key) {
                    return mid;
                }
            }
            return -1;
        }

     

    展开全文
  • 理论就是先找中间的,如果中间数大于大于目标数,那么就只需要找上半份数据折半查找就可以了。一直到找到为止,不用遍历所有数据,效率很高。实现折半查找的方法案例:packagejavalm;publicclassbiSearch{/***@...

    折半查找介绍:

    折半查找,找的是一个有序列表。理论就是先找中间的,如果中间数大于大于目标数,那么就只需要找上半份数据中再折半查找就可以了。一直到找到为止,不用遍历所有数据,效率很高。

    实现折半查找的方法案例:package javalm;

    public class biSearch {

    /**

    * @param args

    */

    /*

    折半查找--当查找表是有序表时,可采用折半查找;

    基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功;

    若给定值K小于中间记录的关键字,则在表的左半区继续查找;

    若给定值K大于中间记录的关键字,则在表的右半区继续查找,不断重复,直到查找成功/失败。

    */

    //折半查找非递归算法

    //查询成功返回该对象的下标序号,失败时返回-1。

    int BiSearch(int r[],int n,int k)

    {

    int low=0;

    int high=n-1;

    while(low<=high)

    {

    int mid=(low+high)/2;

    if(r[mid]==k)

    return mid;

    else

    if(r[mid]

    low=mid+1;

    else

    high=mid-1;

    }

    return -1;

    }

    //折半查找递归算法

    //查询成功返回该对象的下标序号,失败时返回-1。

    int BiSearch2(int r[],int low,int high,int k)

    {

    if(low>high)

    return -1;

    else

    {

    int mid=(low+high)/2;

    if(r[mid]==k)

    return mid;

    else

    if(r[mid]

    return BiSearch2(r,mid+1,high,k);

    else

    return BiSearch2(r,low,mid-1,k);

    }

    }

    public static void main(String[] args) {

    biSearch bs=new biSearch();

    int r[]={1,2,3,4,5};

    System.out.println(bs.BiSearch(r,5,5));

    System.out.println(bs.BiSearch2(r,1,5,5));

    }

    }

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

    2021-09-14 12:26:56
    哈喽,很高兴见到大家,这次是用java语言写的折半查找法,实际上, 小白通过对比C语言里的二分法,小白发现,这两种办法的原理相同。 可以参考高中学的查找零点的办法。 import java.util.Scanner; public class ...
  • java折半查找法

    2021-03-16 20:16:24
    折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=1,上限为h=5,求中点m=(l+h)/2,用X与中点元素am比较,若X等于...
  • java折半查找算法

    2021-04-17 02:47:29
    high 时表示查找区间为空,查找失败 } Java 代码: /** * 二分查找算法 * * @param srcArray 有序数组 * @param target 被查找的元素 * @retur......6 、不断利用循环和折半查找算法查找一个整数 n 是否在一个无序的 ...
  • // 顺序折半查找下标 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 -...
  • Java实现折半查找(二分查找)的递归和非递归算法转 : http://wintys.blog.51cto.com/425414/94051/***名称:BinarySearch*功能:实现了折半查找(二分查找)的递归和非递归算法.*说明:* 1、要求所查找的数组已有序,...
  • java 折半查找法(二分查找)实例,需要的朋友可以参考一下
  • 第1关:折半查找(二分查找) 本关任务:给定一个排好序的数组,然后输入另一个整数,判断该整数在数组的什么位置,返回该整数第一次出现的位置(位置从0开始),否则返回-1。 package step1; public class Task ...
  • 主要介绍了Java数据结构实现折半查找算法过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • java折半查找

    2022-01-10 21:33:38
    java折半查找
  • 本文主要向大家介绍了java语言之实现折半查找算法,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。折半查找(Binary Search)又称为二分查找,其要求数据序列呈线性结构,也就是经过排序的。对于没有...
  • 对一组有序序列进行二分查找,找到元素并输出其索引下标,反之则查找失败
  • Java算法折半查找法

    千次阅读 2020-04-26 10:43:49
    Java 算法折半查找法 算法介绍 折半查找法要求线性表是有序的,即表记录按关键字有序(假设是递增有序的)。 折半查找的基本思路:设 R[low, ···, high] 是当前的查找区间,首先确定该区间的中间位置 mid = ...
  • java实现折半查找

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

    2020-11-05 09:12:13
    折半查找算法: public class hacker_01_zheban { public static void main(String[] args) { int[] arr= {12,10,7,6,2,100}; kuaipai(arr,0,arr.length-1); // 参考我的java快速排序算法 for (int i : arr)...
  • 它的前期是线性表的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储、折半查找的基本思想是:取中间记录作为比较对象,若给定值与中间记录的关键字,则在中间记录的关键字相等,则查找成功;...
  • } //折半的第二种方式 public static int halfSerach_2(int[] arr,int key){ int min = 0,max = arr.length-1,mid; while(min){ mid = (max+min)>>1; if (key>arr[mid]) { min = mid+ 1; }else if(keyarr[mid]) { ...
  • public class biSearch {/*** @param args*//*折半查找--当查找表是有序表时,可采用折半查找;基本思想:在有序表,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功;若给定值K小于中间记录的...
  • 包括常见的排序算法,以及折半查找,首先对要查找的数据排好序,然后用递归调用的方式实现折半查找(包括了两种实现方式)。指定一个排好序的数组和要查找的值,同时指定要查找的左边界和有边界。左右边界要位于数组...
  • 二分查找 又叫折半查找,是一种简单又快速的查找算法。它对要查找的序列有两个要求:一是该序列必须是有序的(即该序列的所有元素都是按照大小关系排好序的,升序和降序都可以,本文假设是升序排列的),二是该...
  • java实现折半排序算法

    2020-09-03 20:01:07
    折半插入排序,又称二分插入排序,是直接插入排序的改良版,也需要执行i-1趟插入,不同之处在于,第i趟插入,先找出第i+1个元素应该插入的的位置,假定前i个数据是已经处于有序状态。
  • java 快速排序 折半查找的界面实现 (递归与分治
  • 算法复杂度:二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果xa[n/2],则只要在数组a的右半部搜索x.时间复杂度无非就是while循环的次数!总共有n个元素...
  • // 折半查找(二分查找) /*--先从数组中间开始找,如果查找的数>中间值,则在后面找;如果查找的数<中间值,则在前面面找 --如果第一次找不到,则二分从后面(前面)的中间继续找,直到起始位置>...
  • 下面的代码展示有简单查找和二分查找(也叫折半查找法),将进行依次分析。 /* 需求:查找某个元素在数组的位置 思路: 遍历数组的每个元素与所要查找的元素进行比较,相同时返回其索引值 步骤: 1.定义...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,920
精华内容 4,768
关键字:

java中折半查找算法

java 订阅