精华内容
下载资源
问答
  • 利用二查找法查找数据
    千次阅读
    2016-12-16 14:33:47

    要求:

    1.随机生成15个不重复的0-100之间的整数组成数组并输出

    2.对数组进行排序

    3.用户输入某一个数据进行查找,查找到后返回该数据以及该数据的位置

    4.若没有查找到则输出没有找到

    代码如下:

    public class ErFenChaZhao {
    	public static void main(String[] args) {
    		//接收产生的随机数组
    		int[] arr = generate();
    		System.out.println("排序前数组(不重复):"+Arrays.toString(arr));
    		//数组排序
    		Arrays.sort(arr);
    		System.out.println("排序后数组(不重复):"+Arrays.toString(arr));
    		//查找数据
    		check(arr);
    	}
    	//产生随机数组0-100不重复
    	public static int[] generate(){
    		Random rand = new Random();
    		int[] arr = new int[15];
    		boolean[] flag = new boolean[100];//给这100个数安装一个开关
    		for(int i = 0;i<arr.length;i++){
    			int index;
    			do{
    				index = rand.nextInt(100);
    			}while(flag[index]);
    			flag[index] = true;
    			arr[i] = index;
    		}
    		return arr;
    	}
    	//传入参数:数组,用户输入并判断,返回查到的数据并且范围数据位置,或没有查找到该数据
    	public static void check(int[] arr){
    		Scanner scan = new Scanner(System.in);
    		System.out.println("请用户输入要查找的数据:");
    		int input = scan.nextInt();//接收数据
    		int start = 0;
    		int end =arr.length-1;
    		boolean k = false;
    		int middle = 0;
    		while(start <= end){
    			middle = (start + end)/2;
    			if(input < arr[middle]){
    				end = middle -1;
    			}else if(input > arr[middle]){
    				start = middle + 1;
    			}else{
    				k = true;
    				break;
    			}
    		}
    		if(k){
    			System.out.println("数据"+input+"位于数组的第"+(middle+1)+"个元素位置处");
    		}else{
    			System.out.println("数据"+input+"不在数组里面");
    		}
    	}
    }

    测试结果如下:

    排序前数组(不重复):[60, 24, 76, 43, 9, 17, 73, 0, 61, 75, 37, 77, 94, 96, 32]
    排序后数组(不重复):[0, 9, 17, 24, 32, 37, 43, 60, 61, 73, 75, 76, 77, 94, 96]
    请用户输入要查找的数据:
    76
    数据76位于数组的第12个元素位置处




    更多相关内容
  • 分查找法

    千次阅读 2020-12-28 22:53:17
    分查找法(Binary Search)算法,也叫折半查找算法。二分查找针对的是一个有序的数据集合,查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将带查找的区间缩小为之前的一半,直到找到要查找的元素...

    一、基本概念

    二分查找法(Binary Search)算法,也叫折半查找算法。二分查找要求数组数据必须采用顺序存储结构有序排列。查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将带查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。二分查找是一种非常非常高效的查询算法,时间复杂度为O(logn)。

    二、算法实现

    之前有写过利用数组进行数据查找的文章,其采用的是二分查找,不过原先的实现代码并不通用,因为源代码只适用于整型数组,倘若要求在浮点数组或者字符串数组中查找,那只能重新编码了。

    因此,对于这种基本逻辑结构雷同、仅有数据类型不同的算法,完全可以采取泛型的手段处理。

    接下来就利用泛型实现通用的二分查找算法。

    注意: 凡是实现了Comparable接口的数据类型(即包装类型,不是基本数据类型),它的数组都能运用泛型方法进行二分查找。

    泛型方法的定义:

    	// 二分查找的入口方法。注意泛型类型T必须实现了接口Comparable
    	// 请求参数为待查找的数组及目标元素,返回参数为目标元素的数组下标(位置)
    	public static <T extends Comparable<T>> int binarySearch(T[] array, T aim);
    

    定义好泛型的规格后,还得在方法体补充详细的代码逻辑,除了要将比较大小的大于号和小于号换成compareTo方法外,整体的查找过程既可沿用原来的for循环语句,又可以采用严谨的递归方式。

    【方法一】:递归方式

    封装了二分查找泛型方法的工具类

    //二分查找算法的工具类。使用了泛型方法
    public class ArrayFind {
    	private static int count; // 查找次数
    
    	// 二分查找的入口方法。注意泛型类型T必须实现了接口Comparable
    	// 请求参数为待查找的数组及目标元素,返回参数为目标元素的数组下标(位置)
    	public static <T extends Comparable<T>> int binarySearch(T[] array, T aim) {
    		count = 0; // 开始查找前先把查找次数清零
    		return binarySearch(array, 0, array.length - 1, aim);//说白了就是对start、end赋值
    	}
    
    	// 使用递归实现的二分查找
    	private static <T extends Comparable<T>> int binarySearch(T[] array, int begin, int end, T aim) {
    		count++; // 查找次数加一
    		if (begin >= end && aim.compareTo(array[begin])!=0) { // 起点和终点都重合了还没找到
    			return -1; // 返回-1表示没找到
    		}
    		//int middle = begin + ((end - begin) >> 1);
    		int middle = (begin + end) / 2; // 计算中间的位置
    		if (aim.compareTo(array[middle]) == 0) { // 找到目标值,返回目标值所处的位置
    			System.out.println("查找次数="+count);
    			return middle;
    		} else if (aim.compareTo(array[middle]) < 0) { // 目标值在前半段,继续查找
    			return binarySearch(array, begin, middle - 1, aim);
    		} else { // 目标值在后半段,继续查找
    			return binarySearch(array, middle + 1, end, aim);
    		}
    	}
    }
    

    对上面代码加以验证;
    步骤:先构造填满元素的数组,然后对其排序,最后再调用ArrayFind的binarySearch方法查找。

    //演示如何使用二分查找法在某个数组里面找到目标值
    public class TestFind {
    
    	public static void main(String[] args) {
    		testIntFind(); // 测试整型数组的查找
    		testStrFind(); // 测试字符串数组的查找
    	}
    	
    	// 测试整型数组的查找
    	private static void testIntFind() {
    		Integer item = 0; // 随机数变量
    		Integer[] numberArray = new Integer[20]; // 随机数构成的数组
    		// 以下生成一个包含随机整数的数组
    		loop: for (int i = 0; i < numberArray.length; i++) {
    			item = new Random().nextInt(100); // 生成一个小于100的随机整数
    			for (int j = 0; j < i; j++) { // 遍历数组进行检查,避免塞入重复数字
    				// 数组中已存在该整数,则重做本次循环,以便重新生成随机数
    				if (numberArray[j] == item) {
    					i--; // 本次循环做了无用功,取消当前的计数
    					continue loop; // 直接继续上一级循环
    				}
    			}
    			numberArray[i] = item; // 往数组填入新生成的随机数
    		}
    		Arrays.sort(numberArray); // 对整数数组排序(默认升序排列)
    		System.out.println();
    		for (int seq=0; seq<numberArray.length; seq++) { // 打印数组中的所有数字
    			System.out.println("序号="+seq+", 数字="+numberArray[seq]);
    		}
    		
    		// 下面通过二分查找法确定目标数字排在第几位
    		Integer aim_item = item; // 最后生成的整数
    		System.out.println("准备查找的目标数字="+aim_item);
    		// 通过泛型的二分查找方法来查找目标数字的位置
    		int position = ArrayFind.binarySearch(numberArray, aim_item);
    		System.out.println("查找到的位置序号="+position);
    	}
    
    	// 测试字符串数组的查找
    	private static void testStrFind() {
    		String item = ""; // 随机字符串变量
    		String[] stringArray = new String[20]; // 随机字符串构成的数组
    		// 以下生成一个包含随机字符串的数组
    		loop: for (int i = 0; i < stringArray.length; i++) {
    			int random = new Random().nextInt(26); // 生成一个小于26的随机整数
    			item = "" + (char) (random + 'A'); // 利用随机数获取从"A"到"Z"的随机字符串
    			for (int j = 0; j < i; j++) { // 遍历数组进行检查,避免塞入重复字符串
    				// 数组中已存在该整数,则重做本次循环,以便重新生成随机字符串
    				if (stringArray[j].equals(item)) {
    					i--; // 本次循环做了无用功,取消当前的计数
    					continue loop; // 直接继续上一级循环
    				}
    			}
    			stringArray[i] = item; // 往数组填入新生成的随机字符串
    		}
    		Arrays.sort(stringArray); // 对字符串数组排序(默认升序排列)
    		System.out.println();
    		for (int seq=0; seq<stringArray.length; seq++) { // 打印数组中的所有字符串
    			System.out.println("序号="+seq+", 字符串="+stringArray[seq]);
    		}
    		
    		// 下面通过二分查找法确定目标字符串排在第几位
    		String aim_item = item; // 最后生成的字符串
    		System.out.println("准备查找的目标字符串="+aim_item);
    		// 通过泛型的二分查找方法来查找目标字符串的位置
    		int position = ArrayFind.binarySearch(stringArray, aim_item);
    		System.out.println("查找到的位置序号="+position);
    	}
    
    }
    

    【方二】:for循环语句

    	
    //二分查找算法的工具类。使用了泛型方法
    public class ArrayFind {
    	private static int count; // 查找次数
    
    	// 二分查找的入口方法。注意泛型类型T必须实现了接口Comparable
    	// 请求参数为待查找的数组及目标元素,返回参数为目标元素的数组下标(位置)
    	//for循环语句
    	public static <T extends Comparable<T>> int binarySearch_1(T[] array, T aim) {
    
    		return binarySearch_1(array, 0, array.length-1, aim);
    	}
    	
    	private static <T extends Comparable <T>> int binarySearch_1(T[] array,int begin,int end, T aim) {
    		int count;
    		int position = 0;
    		
    		for(count = 1; begin <= end; count++) {
    			int middle = (begin + end) / 2;
    			//int middle = begin + ((end - begin) >> 1);
    			if(aim.compareTo(array[middle]) < 0) {
    				end = middle - 1;	
    			}else if(aim.compareTo(array[middle]) > 0) {
    				begin = middle + 1;
    			}else {
    				position = middle;
    				break;
    			}
    		}
    		return position;
    	}
    

    实际上,middle=(start+end)/2 这种写法是有问题的。因为如果 start 和 end 比较大的话,两者之和就有可能会溢出。改进的方法是将 middle 的计算方式写成 start+(end-start)/2。更进一步,如果要将性能优化到极致的话,我们可以将这里的除以 2 操作转化成位运算 start+((end-start)>>1)。因为相比除法运算来说,计算机处理位运算要快得多。

    【补充】:位运算符 之 左右移

    1. 左移(<<)
      参加运算的两个数,换算为二进制(0、1)后,进行左移运算,用来将一个数各二进制位全部向左移动若干位。
      在这里插入图片描述
      注意,观察可以发现,左移一位的结果就是原值乘2,左移两位的结果就是原值乘4。
    2. 右移(>>)
      参加运算的两个数,换算为二进制(0、1)后,进行右移运算,用来将一个数各二进制位全部向右移动若干位。
      在这里插入图片描述
      注意,观察可以发现,右移一位的结果就是原值除2,右移两位的结果就是原值除4,注意哦,除了以后没有小数位的,都是向下取整。

    三、局限性

    1. 二分查找法依赖的是顺序表结构,简单点来说就是数组。主要原因是二分查找方法需要按照下标随机访问元素。如果使用其他数据结构,时间复杂度就会提高。
    2. 二分查找针对的是有序数据。所以二分查找只能在插入、删除操作不频繁,一次排序多次查找的场景中;
    3. 数据量太小不适合二分查找,如果要处理的数据量很小,顺序遍历就够了。不过,如果元素直接的比较操作非常耗时,例如字符串之间的比较,不管数据量大小,都推荐使用二分查找算法。
    4. 数据量太大也不适合用二分查找,因为二分查找依赖于顺序存储结构,要求内存空间连续,如果数据量很大的情况下,可能存在空间不够分配的困难。

    四、简单举例

    1.【详细讲解过程】
    已有9个数字,分别为10,20,30,40,50,60,70,80,90。现需查找数字60。

    首先,用图解理解原理:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    【代码实现】

    		int[] nums = {10,20,30,40,50,60,70,80,90};
    		
    		//要查找的数据
    		int num = 60;
    		
    		//关键的三个变量
    		//1. 最小范围下标
    		int minIndex = 0;
    		//2. 最大范围下标
    		int maxIndex = nums.length - 1;
    		//3. 中间下标
    		int centerIndex = minIndex + ((maxIndex - minIndex) >> 1);
    		
    		while(true) {
    			if(nums[centerIndex] > num) {
    				//中间数据较大
    				maxIndex = centerIndex - 1;
    			}else if(nums[centerIndex] < num) {
    				//中间数据较小
    				minIndex = centerIndex + 1;
    			}else {
    				//找到目标数据,数据位置:centerIndex
    				break;
    			}
    			
    			if(minIndex > maxIndex) {
    				centerIndex = -1;
    				break;
    			}
    			centerIndex = minIndex + ((maxIndex - minIndex) >> 1);
    		}
    		System.out.println("目标下标位置:" + centerIndex);
    

    运行结果:

    目标下标位置:5
    

    下面这幅图是查找不到相应数据的图解:
    在这里插入图片描述

    2.已经有10个数字,分别是6,8,4,5,9,10,18,17,16,20,现需要查找数字20。

    public static int binarySearch(int[] arr, int aim) {
    		//1.定左右标尺
    		int begin = 0;
    		int end = arr.length -1;
    		
    		//2.标尺不相错,一直循环:根据中值(a、算中值,b、和中值对比),调整标尺返回结果
    		while(begin <= end) {//擦肩而过,就退出循环
    			int middle = begin + ((end - begin) >> 1);
    			
    			if(aim < arr[middle]) {//往左走
    				end = middle - 1;
    			}else if(aim > arr[middle]) {//往右走
    				begin = middle + 1;
    			}else {
    				return middle;
    			}
    
    		}
    		return -1;
    	}
    
    public static void main(String[] args) {
    		int[] array = {6,8,4,5,9,10,18,17,16,20};
    		Arrays.sort(array);
    		for(int seq = 0; seq < array.length; seq++) {
    			System.out.println("序号:" + seq + ",对应的值:" + array[seq]);
    		}
    		int aim = 20;
    		System.out.println(ArrayFind_1.binarySearch(array,aim));
    	}
    		
    

    五、总结

    • 确定查找的范围

    • 计算中间的下标 minIndex + ((maxIndex - minIndex) >> 1)

    • 比较中间下标数据,中间下标数据较大,则最大下标等于中间下标-1;
      比较中间下标数据,中间下标数据较小,则最小下标等于中间下标+1;

    • 但最小下标 > 最大下标时,说明数据是不存在的。

    展开全文
  • 注意:折半查找法仅适用于已有顺序的数组、数据进行操作!!! 很显然,折半查找法相对于其他查找方法例如顺序查找法效率要高很多; 下面我们来实际操作一下,了解二分查找的奥义。 例如:要在数组arr[]={8,7,9,6,...
  • 编写程序对数据序列采用二查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
  • 折半查找算法是对于有序的序列而言的,每次查找后折半,大概缩短了一半的查找区间,是一种效率较高的查找算法。 要求: list必须是顺序结构,且按照关键词大小进行有序排列。 思路: 在有序序列中查找元素,每次取...

    折半查找/二分查找算法

    给出一个list和一个元素,判断出list中是否存在该元素

    浅短理解:

    折半查找算法是对于有序的序列而言的,每次查找后折半,大概缩短了一半的查找区间,是一种效率较高的查找算法。

    要求:

    list必须是顺序结构,且按照关键词大小进行有序排列。

    思路:

    在有序序列中查找元素,每次取序列中间的元素,如果与要查找元素相等,程序结束;
    如果查找元素大于中间元素,则取中间元素后面的序列再进行如上的查找;
    如果查找元素小于中间元素,则取中间元素前面的序列再进行如上的查找;
    直到找到元素相等,查找成功,或者序列为空,查找失败,程序结束。
    在这里插入图片描述
    python版本:Python2.7.5

    # _*_ encoding:utf-8 _*_
    
    def binary_search(lists, key, left, right):
    	'''
    	lists:有序序列/list
    	key:要查找的元素
    	left:查找的起始位置
    	right:查找的结束位置 -方便使用递归
    	return:返回查找元素下标
    	'''
    	# 查找的起始位置大于等于结束位置,查找失败程序结束
    	if left >= right:
    		return None
    	mid = (right - left) // 2 + left		# 折半,中间元素下标
    
    	if lists[mid] > key:
    		# 中间元素大于查找元素,则查找前半序列
    		return binary_search(lists, key, left, mid - 1)
    	elif lists[mid] < key:
    		# 中间元素小于查找元素,则查找后半序列
    		return binary_search(lists, key, mid + 1, right)
    	else:
    		# 中间元素等于查找元素,程序结束返回下标
    		return mid
    
    
    if __name__ == '__main__':
    
    	lt = [3,7,10,11,20,33,36,40,88]
    	index = binary_search(lt, 33, 0, len(lt))
    
    	print u'元素位置:{}'.format(index) if index else u'没有找到该元素'
    

    运行结果

    在这里插入图片描述

    文章中有不足之处请多多指教,欢迎讨论,共同学习,共同进步

    展开全文
  • Java实现二分查找法

    千次阅读 2021-03-23 13:35:53
    通常,大多数编程语言都支持用于搜索集合中数据的线性搜索,二进制搜索和哈希技术。我们将在后续教程中学习哈希。 Java中的二进制搜索 线性搜索是一项基本技术。在此技术中,顺序遍历数组,并将每个元素与键进行...

    本教程将介绍Java中的二分查找和递归二分查找算法。

    Java中的二分查找是一种用于在集合中查找目标值或键的技术。它是一种使用“分而治之”技术查找关键字的技术。

    应用二分查找来查找关键字的集合需要按升序排序。

    通常,大多数编程语言都支持用于搜索集合中数据的线性搜索,二分查找和哈希技术。我们将在后续教程中学习哈希。

     

    Java中的二分查找

    线性查找是一项基本技术。在此技术中,顺序遍历数组,并将每个元素与键进行比较,直到找到键或到达数组的末尾为止。

    线性查找在实际应用中很少使用。二分查找是最常用的技术,因为它比线性查找快得多。

    Java提供了三种实现二分查找的方式:

    1. 使用迭代方法
    2. 使用递归方法
    3. 使用Arrays.binarySearch()方法。

    在本教程中,我们将实现和讨论所有这三种方法。

    Java中的二分查找算法

    在二分查找方法中,将集合重复地分成两半,并根据关键字是小于还是大于集合的中间元素来在集合的左半部分或右半部分中搜索关键元素。

    一种简单的二分查找算法如下:

    1. 计算集合的中间元素。
    2. 将关键项与中间元素进行比较。
    3. 如果key = middle元素,则返回找到的键的中间索引位置。
    4. 否则,如果键>中间元素,则键位于集合的右半部分。因此,在集合的下半部分(右)重复步骤1到3。
    5. 其他键<中间元素,则键在集合的上半部分。因此,您需要在上半部分重复二分查找。

    从上述步骤中可以看到,在二分查找中,在第一次比较之后,集合中的一半元素将被忽略。

    注意,相同的步骤顺序适用于迭代和递归二分查找。

    让我们使用一个例子来说明二分查找算法。

    例如,采用10个元素的以下排序数组。

    10个元素的排序数组

    让我们计算数组的中间位置。

    中= 0 + 9/2 = 4

    数组的中间位置

    #1)键= 21

    首先,我们将键值与[mid]元素进行比较,发现在mid = 21处的元素值。

    键= 21

    因此,我们发现密钥= [mid]。因此,可以在数组中的位置4找到密钥。

    #2)键= 25

    键= 25

    我们首先将键值与中值进行比较。由于(21 <25),我们将直接在数组的上半部分搜索键。

    在数组的上半部分搜索键。

    现在,我们再次找到阵列上半部分的中间部分。

    中= 4 + 9/2 = 6

    位置[mid]处的值= 25

    位置[中]的值= 25

    现在,我们将键元素与中间元素进行比较。因此(25 == 25),因此我们在位置[mid] = 6处找到了密钥。

    因此,我们反复划分数组,并通过将键元素与中间元素进行比较,来确定要在哪一半中搜索键。在时间和正确性方面,二进制搜索效率更高,并且速度也快得多。

    Java实现二分查找

    使用上述算法,让我们使用迭代方法在Java中实现二分查找程序。在此程序中,我们以一个示例数组为例,并对该数组执行二分查找。

    package BinarySearch;
    
    import java.util.*;
    
    class BinarySearchIterative {
    	public static void main(String args[]) {
    		int numArray[] = { 5, 10, 15, 20, 25, 30, 35 };
    		System.out.println("The input array: " + Arrays.toString(numArray));
    		// key to be searched
    		int key = 20;
    		System.out.println("\nKey to be searched=" + key);
    		// set first to first index
    		int first = 0;
    		// set last to last elements in array
    		int last = numArray.length - 1;
    		// calculate mid of the array
    		int mid = (first + last) / 2;
    		// while first and last do not overlap
    		while (first <= last) {
    			// if the mid < key, then key to be searched is in the first half of array
    			if (numArray[mid] < key) {
    				first = mid + 1;
    			} else if (numArray[mid] == key) {
    				// if key = element at mid, then print the location
    				System.out.println("Element is found at index: " + mid);
    				break;
    			} else {
    				// the key is to be searched in the second half of the array
    				last = mid - 1;
    			}
    			mid = (first + last) / 2;
    		}
    		// if first and last overlap, then key is not present in the array
    		if (first > last) {
    			System.out.println("Element is not found!");
    		}
    	}
    }


    输出:

    输入数组:[5、10、15、20、25、30、35]
    要搜索的键= 20
    在索引:3处找到元素

    输出-二进制搜索实现Java

    上面的程序显示了二进制搜索的迭代方法。最初,声明一个数组,然后定义要搜索的键。

    在计算数组的中位数之后,将键与中位数元素进行比较。然后根据键是小于还是大于键,分别在数组的下半部分或上半部分中搜索该键。

    Java中的递归二分查找

    您还可以使用递归技术执行二分查找。在此,递归调用二分查找方法,直到找到关键字或整个列表用尽。

    下面给出了实现递归二分查找的程序:

    package BinarySearch;
    
    import java.util.*;
    
    class BinarySearchRecursive {
    	// recursive method for binary search
    	public static int binary_Search(int intArray[], int low, int high, int key) {
    		// if array is in order then perform binary search on the array
    		if (high >= low) {
    			// calculate mid
    			int mid = low + (high - low) / 2;
    			// if key =intArray[mid] return mid
    			if (intArray[mid] == key) {
    				return mid;
    			}
    			// if intArray[mid] > key then key is in left half of array
    			if (intArray[mid] > key) {
    				return binary_Search(intArray, low, mid - 1, key);// recursively search for key
    			} else // key is in right half of the array
    			{
    				return binary_Search(intArray, mid + 1, high, key);// recursively search for key
    			}
    		}
    		return -1;
    	}
    
    	public static void main(String args[]) {
    		// define array and key
    		int intArray[] = { 1, 11, 21, 31, 41, 51, 61, 71, 81, 91 };
    		System.out.println("Input List: " + Arrays.toString(intArray));
    		int key = 31;
    		System.out.println("\nThe key to be searched:" + key);
    		int high = intArray.length - 1;
    		// call binary search method
    		int result = binary_Search(intArray, 0, high, key);
    		// print the result
    		if (result == -1)
    			System.out.println("\nKey not found in given list!");
    		else
    			System.out.println("\nKey is found at location: " + result + " in the list");
    	}
    }
    

    输出:

    输入列表:[1,11,21,31,41,51,61,71,81,91
    要搜索的密钥:
    密钥位于列表中的位置3

    输出-Java中的递归二进制搜索

    使用Arrays.binarySearch()方法。

    Java中的Arrays类提供了一种'binarySearch()'方法,该方法在给定的Array上执行二分查找。此方法将数组和要搜索的键作为参数,并返回键在数组中的位置。如果找不到该键,则该方法返回-1。

    下面的示例实现Arrays.binarySearch()方法。

    package BinarySearch;
    
    import java.util.Arrays;
    
    class BinarySearchArrays {
    	public static void main(String args[]) {
    		// define an array
    		int intArray[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
    		System.out.println("The input Array : " + Arrays.toString(intArray));
    		// define the key to be searched
    		int key = 50;
    		System.out.println("\nThe key to be searched:" + key);
    		// call binarySearch method on the given array with key to be searched
    		int result = Arrays.binarySearch(intArray, key);
    		// print the return result
    		if (result < 0)
    			System.out.println("\nKey is not found in the array!");
    		else
    			System.out.println("\nKey is found at index: " + result + " in the array.");
    	}
    }

    输出:

    输入Array:[10,20,30,40,50,60,70,80,90]
    要搜索的键:50
    键位于数组的索引:4处。

    输出-使用Arrays.binarySearch()方法。

    经常问的问题

    问#1)您如何编写二分查找?

    答:二分查找通常是通过将数组分成两半来执行的。如果要搜索的键大于中间元素,则通过进一步划分和搜索子数组直到找到键来搜索数组的上半部分。

    同样,如果键小于中间元素,则在数组的下半部分搜索键。

    问#2)二分查找在哪里使用?

    答:二分查找主要用于在软件应用程序中搜索排序的数据,尤其是在存储空间紧凑且有限的情况下。

    Q#3)二分查找的最大作用是什么?

    答:二分查找的时间复杂度为O(logn),其中n是数组中元素的数量。二分查找的空间复杂度为O(1)。

    问#4)二分查找是否递归?

    答:可以。由于二分查找是分而治之策略的一个示例,因此可以使用递归来实现。我们可以将数组分成两半,然后调用相同的方法来一次又一次地执行二分查找。

    问#5)为什么称其为二分查找?

    答:二分查找算法使用分而治之的策略,该策略反复将数组切成两半或两部分。因此,它被称为二分查找。

    结论

    二分查找是Java中经常使用的搜索技术。执行二分查找的要求是,数据应按升序排序。

    可以使用迭代或递归方法来实现二分查找。Java中的Arrays类还提供了'binarySearch'方法,该方法对Array执行二分查找。

    在后续的教程中,我们将探讨Java中的各种排序技术。

    展开全文
  • 项目背景: 从一个文件获取10万笔... *如果源数据是有序的,则二分查找法效率高  *如果源数据是无序的,则顺序查找法效率高 原因: 1、字符串排序非常耗时 2、二分查找法需要先排序 执行结果 ------------...
  • 折半查找法又称为二分查找法,该方法要求带查找的表是顺序存储结构并且表中的关键字大小有序排列。 查找过程: 先确定待查记录所在的区间,然后逐渐通过待查找值与区间中间值进行比较进而调整区间大小,不断缩小范围...
  • 分查找法最大最小比较次数

    千次阅读 2019-09-10 11:11:21
    说说「二分查找法」。
  • 数据结构之二分查找

    千次阅读 2019-01-14 15:57:29
    分查找是一种非常简单易懂的快速查找算法,生活中到处可见。比如有一个0-99之间的数组,随便取一个数,每猜一次都告诉你大了还似乎小了直到猜中为止。比如这个数是33 第一次 0-99 中间数是49 49&gt;33 第二次 ...
  • 顺序查找通常分为一般的无序线性表的顺序查找按关键字有序的顺序表的顺序查找。下面分别进行讨论。 1.1、一般线性表的顺序查找 作为一种最直观的查找方法,其基本思想是从线性表的一端开始,逐个检查关键字...
  • 静态查找表——基于线性表的查找法 动态查找表——基于树表的查找法 哈希表——计算式查找法 基本概念 查找表 由同一类型的数据元素(记录)构成的集合。 查找的定义 给定一个值 key,在含有 n 个记录的表中找出...
  • 数据结构】顺序查找和折半查找

    千次阅读 多人点赞 2021-04-03 08:07:36
    数据结构之查找算法 摘要:在本篇文章中,主要讲述了在数据结构中所涉及的几大查找算法,包括:顺序查找、折半查找、分块查找和散列表查找。这些查找方式都是数据结构中最基本的查找方式,并且在数据结构中运用广泛...
  • C 二分查找算法.rar

    2019-07-10 09:23:17
    C 二查找算法源码实例,编写程序对数据序列采用二查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
  • 分查找算法例题

    千次阅读 2021-04-21 14:26:32
    目录一、问题描述二、实现思路三、解题代码四、运行结果 一、问题描述   对于给定11个数据...  对于给定11个数据元素的有序表:(2,3,10,15,20,25,28,29,30,35,40),采用二分查找,若查找给定值为20的
  • 使用二分法查找的必要条件: 1、数组有序 2、注意数据类型是有范围的,不要溢出。 3、采用L+(R-L)/2表达式更合适 4、注意:start = mid +1 和 end=mid -1,防止死循环 5、数据量不可过大 1024个人,有一个...
  • 数据结构》-第七章 查找(习题)

    千次阅读 2021-08-27 22:39:13
    前几章这些数据结构的产生相应运算—查找。关于查找的不同算法为每年考试考查的重点,因此需要重点把握各个结构包括的查找方法及查找删除等操作的过程。散列结构主要,应学握散列表的构造、冲突处理方法(各种...
  • 查找过程中,往往是依据数据元素的某个数据项进行查找,这个数据项通常是数据的关键字。 关键字:是数据元素中某个数据项的值,用以标识一个数据元素。 若关键字能标识唯一的一个数据元素,则称谓主关键字。 若关键字能...
  • 分查找法过程详解

    千次阅读 2019-04-25 16:32:46
    现在我们来玩一个猜数的游戏,假设有一个人要我们猜0-99之间的一个数。那么最好的方法就是从0-99的中间数49...二分查找操作的数据集是一个有序的数据集。开始时,先找出有序集合中间的那个元素。如果此元素比要查找...
  • 例如,在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前,需要首先该表中的数据按照所查的关键字进行排序:{5,13,19,21,37,56,64,75,80,88,92}。 在折半查找之前查找...
  • 数据结构>折半查找算法实现

    千次阅读 2020-10-31 23:01:56
    提示:本篇主要是本小白大学期间对数据结构实验的一些基本代码功能实现,希望一同数据结构的伙伴有所帮助。 提示:以下是本篇文章正文内容,下面案例可供参考 一、折半查找算法(采用顺序表存储结构) 要求:编写...
  • 查找:给定一个值,在查找表中确定一个其关键字与给定值得数据元素(或记录)。 查找包含有一下几种操做: 1、查询某个“特定”的数据元素是否在查找表当中; 2、检索某个“特定”的数据元素的相关属性; 3、在查找...
  • 对分查找

    千次阅读 2019-03-16 14:59:57
    对分查找要求顺序结构存储 int main() { int i; int n = 5; int arr[30] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}; i = binarySearch(arr,30,n); printf("...
  • 分查找(折半查找)详解

    千次阅读 多人点赞 2021-01-10 01:05:54
    分查找的引入 说到二分查找相信大家都很熟悉,最经典的例子就是猜数字问题: 从1到100中,随机抽取一个数字。...但如果说使用二分查找就不一样了,二的猜就快多了。 假设现在产生了一个随机值:37 ...
  • 在有序表{7,14,18,21,23,29,31,35,38}中查找18. 【解析】 对于折半查找有序表里面其中的一个元素的话我们需要注意以下几点 &gt;首先我们需要将表中的元素从小到大排序,由于题目中已经说了是有序表所以我们不...
  • 算法(Algorithm),是程序设计的灵魂,它是利用系统的方法描述...本系列文章旨在用C语言解释算法的作用,分析包括排序算法、查找算法、迭代算法、递推算法、 递归算法、枚举算法、贪心算法、回溯算法、矩阵算法等。
  • 2.基本思想:选定这批数据中居中间位置的一个数与查找数比较,看是否为所找之数,若不是,利用数据的有序性,可以决定所找的数是在选定数之前还是之后,从而很快可以将查找范围缩小一半,就是一半一半的缩小范围,...
  • 数据结构 查找-详细介绍

    千次阅读 2020-12-10 14:48:50
    2.查找表的数据结构表示 (1)动态查找表和静态查找表 若在查找的同时对表做修改操作(如插入和删除),则相应的表称之为动态查找表。否则称之为静态查找表。 (2)内查找和外查找 若整个查找过程都在内存进行,则称...
  • 数据结构–七大查找算法总结

    万次阅读 多人点赞 2018-08-06 17:13:43
    数据结构–七大查找算法总结 2017年08月15日 21:06:17 阅读数:10610 ...
  • 分查找法-java实现

    千次阅读 2015-07-08 16:59:06
    分查找法 java

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 152,357
精华内容 60,942
关键字:

对分法查找数据