精华内容
下载资源
问答
  • java实现二分查找-两种方式

    万次阅读 多人点赞 2017-10-08 20:02:02
    本文就介绍两种方法 二分查找算法思想 有序的序列,每次都是以序列的中间位置的数来与待查找的关键字进行比较,每次缩小一半的查找范围,直到匹配成功。 一个情景:将表中间位置记录的关键字与查找关键字...

    二分查找是一种查询效率非常高的查找算法。又称折半查找。

    起初在数据结构中学习递归时实现二分查找,实际上不用递归也可以实现,毕竟递归是需要开辟额外的空间的来辅助查询。本文就介绍两种方法


    二分查找算法思想


    有序的序列,每次都是以序列的中间位置的数来与待查找的关键字进行比较,每次缩小一半的查找范围,直到匹配成功。


    一个情景:将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。



    二分查找图示说明


    图片来源百度图片,感谢分享者


    二分查找优缺点


    优点是比较次数少,查找速度快,平均性能好;

    其缺点是要求待查表为有序表,且插入删除困难。

    因此,折半查找方法适用于不经常变动而查找频繁的有序列表。



    使用条件:查找序列是顺序结构,有序。



    java代码实现

    使用递归实现

    	/**
    	 * 使用递归的二分查找
    	 *title:recursionBinarySearch
    	 *@param arr 有序数组
    	 *@param key 待查找关键字
    	 *@return 找到的位置
    	 */
    	public static int recursionBinarySearch(int[] arr,int key,int low,int high){
    		
    		if(key < arr[low] || key > arr[high] || low > high){
    			return -1;				
    		}
    		
    		int middle = (low + high) / 2;			//初始中间位置
    		if(arr[middle] > key){
    			//比关键字大则关键字在左区域
    			return recursionBinarySearch(arr, key, low, middle - 1);
    		}else if(arr[middle] < key){
    			//比关键字小则关键字在右区域
    			return recursionBinarySearch(arr, key, middle + 1, high);
    		}else {
    			return middle;
    		}	
    		
    	}

    不使用递归实现(while循环)

    	/**
    	 * 不使用递归的二分查找
    	 *title:commonBinarySearch
    	 *@param arr
    	 *@param key
    	 *@return 关键字位置
    	 */
    	public static int commonBinarySearch(int[] arr,int key){
    		int low = 0;
    		int high = arr.length - 1;
    		int middle = 0;			//定义middle
    		
    		if(key < arr[low] || key > arr[high] || low > high){
    			return -1;				
    		}
    		
    		while(low <= high){
    			middle = (low + high) / 2;
    			if(arr[middle] > key){
    				//比关键字大则关键字在左区域
    				high = middle - 1;
    			}else if(arr[middle] < key){
    				//比关键字小则关键字在右区域
    				low = middle + 1;
    			}else{
    				return middle;
    			}
    		}
    		
    		return -1;		//最后仍然没有找到,则返回-1
    	}

    测试

    测试代码:

    	public static void main(String[] args) {
    
    		int[] arr = {1,3,5,7,9,11};
    		int key = 4;
    		//int position = recursionBinarySearch(arr,key,0,arr.length - 1);
    		
    		int position = commonBinarySearch(arr, key);
    
                   if(position == -1){
    			System.out.println("查找的是"+key+",序列中没有该数!");
    		}else{
    			System.out.println("查找的是"+key+",找到位置为:"+position);
    		}
    		
    	}

    recursionBinarySearch()的测试:key分别为0,9,10,15的查找结果

    查找的是0,序列中没有该数!
    
    查找的是9,找到位置为:4
    
    查找的是10,序列中没有该数!
    
    查找的是15,序列中没有该数!
    

    commonBinarySearch()的测试:key分别为-1,5,6,20的查找结果

    查找的是-1,序列中没有该数!
    
    查找的是5,找到位置为:2
    
    查找的是6,序列中没有该数!
    
    查找的是20,序列中没有该数!
    


    时间复杂度

    采用的是分治策略

    最坏的情况下两种方式时间复杂度一样:O(log2 N)


    最好情况下为O(1)


    空间复杂度

      算法的空间复杂度并不是计算实际占用的空间,而是计算整个算法的辅助空间单元的个数

    非递归方式:
      由于辅助空间是常数级别的所以:
      空间复杂度是O(1);

    递归方式:

     递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的:
     空间复杂度:O(log2N )



    展开全文
  • Java 中的两种查找算法方式

    万次阅读 2017-12-14 11:22:42
    // 自定义成员方法来描述线性查找,要求在指定的数组中查找指定的元素并返回下标 public static int findOut(int[] arr, int data) { for (int i = 0; i ; i++) { if (data == arr[i]) { return i; }
    public class TestFind {
    
    	// 自定义成员方法来描述线性查找,要求在指定的数组中查找指定的元素并返回下标
    	public static int findOut(int[] arr, int data) {
    		for (int i = 0; i < arr.length; i++) {
    			if (data == arr[i]) {
    				return i;
    			} else {
    				System.out.println("查找失败!没有该元素!");
    			}
    		}
    		return -1;
    	}
    
    	// 自定义成员方法来描述二分查找算法,要求在指定的数组中查找指定的元素并返回下标
    	public static int findBinary(int[] arr, int left, int right, int data) {
    		// 数组中至少有一个元素时才需要查找
    		if (left <= right) {
    			// 1.计算中间元素的下标并记录
    			int p = (left + right) / 2;
    			// 2.使用目标元素与中间元素比较大小,若相等则直接返回当前下标表示查找成功
    			if (data == arr[p]) {
    				return p;
    			}
    			// 3.若目标元素小于中间元素,则去中间元素的左边查找,重复上述过程,使用递归
    			else if (data < arr[p]) {
    				return findBinary(arr, left, p - 1, data);
    			}
    			// 4.若目标元素大于中间元素,则去中间元素的右边查找,重复上述过程,使用递归
    			else {
    				return findBinary(arr, p + 1, right, data);
    			}
    		} else {
    			return -1;
    		}
    
    	}
    
    	public static void main(String[] args) {
    		int[] arr = { 10, 20, 30, 40, 50, 60 };
    		int num = 50;
    		int len = arr.length;
    		int p = findBinary(arr, 0, len, num);
    		System.out.println("当前元素的下标在数组中的位置是:" + p);
    	}
    
    }
    

    展开全文
  • 二分查找两种实现方式JAVA

    千次阅读 2015-08-11 22:22:45
    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好...否则利用中间位置记录将表分成前、后个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上

    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    条件是:1.必须采用顺序存储结构
    2.必须按关键字大小有序排列。

    下面看代码:

    
    public class BinarySearch {
        /**
         * 非递归方法,利用while循环
         * @param arr
         * @param des
         * @return
         */
        public static int binarySearch(int[] arr,int des){
            int low = 0;
            int high = arr.length-1;
            while(low<=high){
                int middle = (low+high)/2;
                if (arr[middle] == des) {
                    return middle;
                }else if (arr[middle]<des) {
                    low = middle+1;
                }else {
                    high = middle-1;
                }
            }
            return -1;
        }
        /**
         * 递归查找
         * @param arr
         * @param des
         * @param low
         * @param high
         * @return
         */
        public static int binarySearch(int[] arr,int des,int low,int high){
            int middle = (low+high)/2;
            if (des<arr[low]||des>arr[high]||low>high) {
                return -1;
            }
            if (arr[middle]<des) {
                return binarySearch(arr, des, middle+1, high);
            }else if (arr[middle]>des) {
                return binarySearch(arr, des, low, middle-1);
            }else{
            return middle;
            }
        }
    
        public static void main(String[] args){
            int[] arr = {1,2,3,4,5,6,7,8,11,15,17};
            int des = 15;
            System.out.println(binarySearch(arr, des));
            System.out.println(binarySearch(arr, des, 0, 10));
    
        }
    
    }
    
    展开全文
  • public class BinarySearch { public static void main(String[] args) { int[] arr = {1,3,5,7,9,11,13,15,17}; System.out.println(search(arr,13)); System.out.println(search1(arr,1,0,arr.length-1)
    public class BinarySearch {
    	
    	public static void main(String[] args)
    	{
    		int[] arr = {1,3,5,7,9,11,13,15,17};
    		System.out.println(search(arr,13));
    		System.out.println(search1(arr,1,0,arr.length-1));
    	}
    	
    	
    	public static int search(int[] arr,int n)//非递归
    	{
    		int low = 0;
    		int high = arr.length-1;
    		while(low<=high)
    		{
    			int mid = (low+high)/2;
    			if(arr[mid]==n)
    				return mid;
    			if(arr[mid]<n)
    			{
    				low=mid+1;
    				
    			}
    			else if(arr[mid]>n)
    			{
    				high=mid-1;
    			}
    		}
    		return -1;
    		
    	}
    	public static int search1(int[] arr,int n,int begin,int end)//递归
    	{
    	
    		
    			int mid=(begin+end)/2;
    			if(n<arr[begin] || n>arr[end] || arr[begin]>arr[end])
    			{
    				return -1;
    			}
    			if(arr[mid]<n)
    			{
    				return search1(arr,n,mid+1,end);
    			}
    			else if(arr[mid]>n)
    			{
    				return search1(arr,n,begin,mid-1);
    			}
    			else
    				return mid;
    	
    	}
    
    }

    展开全文
  • java如何获取随机数(两种方式

    万次阅读 多人点赞 2018-10-01 12:37:21
    在小的知识,都有深挖之价值。...我还是放弃了查找笔记,跑去Google了,所以我决定建立电子笔记,记录那些小知识点。 //获取100以内的随机数 package com.isea.java; import java.util.Random; public ...
  • 二分法查找是经典算法,这篇博客用循环和递归两种方式实现了二分法查找。这篇博客有完整的代码实现以及查找过程的文字详述。
  • 二分查找 算法思想:又叫折半查找,要求待查找的序列有序。每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分...
  • java中获取控制台输入的两种方式

    万次阅读 2016-08-24 19:35:37
    第一种方式:比较传统的方式,得到字符串后要另行判断、转换 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class MainRun { /** * @param ...
  • java用户密码摘要加盐的两种方式

    千次阅读 2015-08-13 11:13:05
    一般采用MD5或者SHA生成摘要,这种方式具有方便、快速而且几乎不可还原性。 但是对相同数据返回的摘要信息永远是一样的。如果某人有DB的权限,...有两种加盐方式: 1、通过用户名+用户密码生成加密摘要,因为用户名
  • java中线性表的两种实现方式区别

    千次阅读 2016-10-06 10:38:24
    注意:线性表的两种实现->顺序实现和链式实现 线性表的两种实现   顺序表 链表 空间性能 顺序表的存储空间是静态分布的,需要一个固定的数组,总有部分数组元素要浪费 链表...
  • 前言:公司开发的框架基于springboot深度封装,只能使用java bean的方式进行项目配置。 1.引入POM坐标,需要同时引入通用mapper和jpa tk.mybatis mapper 3.4.0 javax.persistence ...
  • 二分查找算法(递归与非递归两种方式) 非递归方式完成二分查找法。java代码如下所示。 public class BinarySearchUtil { /** * 二分查找普通实现。 * @param srcArray 有序数组 * @param key 查找元素 * @...
  • Java实现折半查找

    千次阅读 2018-03-30 20:15:21
    二分查找:每一次查找,将查找的区间从中间分为部分,取其中一部分再次进行这样的查找。 折半查找是一高效的查找方法。它可以明显减少比较次数,提高查找效率。 但是,折半查找的先决条件是查找表中的数据元素...
  • Java 查找算法

    万次阅读 2015-07-08 19:49:15
    二分查找 Hash表 二叉树 B Tree
  • java打印日志的几种方式

    千次阅读 2018-07-19 14:25:08
    Java 中实现记录日志的方式有很多, 1. 最简单的方式,就是system.print.out ,err 这样直接在控制台打印消息了。 2. java.util.logging ; 在JDK 1.4 版本之后,提供了日志的API ,可以往文件中写日志了。 3....
  • java -- Map集合取出元素的两种方式

    千次阅读 2017-05-19 18:53:34
    第一种方式:keySet() 方法:  先获取map集合中的键存放进set集合中。通过Set集合的迭代器取出Set集合中键, 通过map的get(key)方法获取键对应的值。 import java.util.*; class KeySetDemo { public static ...
  • Java语言实现线性查找和二分法查找

    千次阅读 2020-09-27 17:40:46
    Java语言实现线性查找和二分法查找 (查找算法) 线性查找(顺序查找) 定义: 在一列给定的值中进行搜索,从一端开始逐一检查每个元素,直到找到所需元素的过程。 本质: 如果查找池是某种类型的一个表,比如一个数组...
  • java实现二分查找

    千次阅读 2017-12-25 17:01:18
    二分查找的简单用法1,二分查找的思想二分查找是一高效的查找算法。它比顺序查找快的多,虽然它需要的条件是数组是有序的。 在查找时,我们先将被查找的数和数组的中间键比较,因为数组是有序的,所有若被查找的...
  • Java在字符串中查找匹配的子字符串

    万次阅读 多人点赞 2017-05-07 15:25:25
    Java在字符串中查找匹配的子字符串
  • Java两种处理异常方法的区别

    万次阅读 多人点赞 2017-11-26 18:02:32
    我的博客什么是异常简单来说,java程序在运行期间发生的问题就是异常。在Java中,把异常信息封装成了一个类,当出现了问题时,就会创建异常类对象并抛出异常相关信息(如异常出现的位置、原因等等)。在Java中使用...
  • java中字符串查找与提取

    万次阅读 2016-05-12 20:33:30
    java String查找与提取 四方法
  • import java.util.HashMap;import demo6.LinkReverse2.Node; /** * 判断链表是否有环的方法 * @author mengfeiyang * */ public class LinkLoop { public static boolean hasLoop(Node n){ //定义个指
  • Java实现指定目录下的文件查找

    万次阅读 2020-11-27 18:35:02
    入门Java实现文件的查找功能较为简单,主要有以下两种: 1.给出文件名,查找目录及其子目录中是否存在 2.给出后缀名,查找目录及其子目录中相关的文件 题型一: 题目:在指定目录下查找一个文件,如果目录或子目录下...
  • Java 定时任务的几实现方式

    万次阅读 多人点赞 2017-06-03 22:04:51
    JAVA实现定时任务的几种方式@(JAVA)[spring|quartz|定时器]  近期项目开发中需要动态的添加定时任务,比如在某个活动结束时,自动生成获奖名单,导出excel等,此类任务由于活动时间是动态的,不能把定时任务配置在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 457,867
精华内容 183,146
关键字:

java查找的两种基本方式是什么

java 订阅