首页 > 代码库 > 基础知识(03) -- 二分法查询
基础知识(03) -- 二分法查询
二分法是当数据量很大时适宜采用,但是采用二分法的前提是:数据是有序不重复的。
二分法查找又称为折半查询,顾名思义就是从中间开始比较查找,其基本思路是: 假设数据时按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查询成功;若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止。
在java.util包下有一个Arrays类,里面就提供了二分法查询的方法,可以去看看具体的源代码是如何实现的:
查看java.util.Arrays中的binarySearch(int[] a,int key)方法:
源码如下:
1 //使用二分搜索法来搜索指定的int型数组,已获取指定的key值在数组中的下标 2 public static int binarySearch(int[] a, int key) { 3 //调用内部方法 4 return binarySearch0(a, 0, a.length, key); 5 }
1 //JDK提供的二分法搜索源码 2 private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) { 3 int low = fromIndex; //低位指针 4 int high = toIndex - 1; //高位指针 5 //当 低位指针的值 大于 高位指针的值时退出while循环 6 while (low <= high) { 7 int mid = (low + high) >>> 1; //取中间值 8 int midVal = a[mid]; 9 10 if (midVal < key) 11 low = mid + 1; 12 else if (midVal > key) 13 high = mid - 1; 14 else 15 return mid; // key found 16 } 17 return -(low + 1); // key not found. 18 }
基础知识(03) -- 二分法查询
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。