首页 > 代码库 > 二分查找法
二分查找法
二分查找法,顾名思义,是一种一分为二的查找算法,适用于已排序的数组(大数据量),快速地找到所查找数的位置。
源代码:
Java代码
- /**
- * @param i 数组
- * @param key 要查找的Key
- * @return
- */
- static int binarySearch(int[] i, int key){
- Arrays.sort(i);
- int low = 0;
- int high = i.length - 1;
- //int mid = (low + high)/2;
- while(low <= high){ // 计算条件,数组低下标和高下标一直在计算中变化
- int mid = (low + high)>>1; // 使用>>比除法计算效率高
- if(key > i[mid]){
- low = mid + 1;
- } else if(key < i[mid]) {
- high = mid - 1;
- } else {
- return mid;
- }
- }
- return -1;
- }
原理:
在数组中搜索给定Key时,先确定是有序数组,然后定义数组的最高下标和最低下标high、low,再求出数组的中间下标mid=(low+high)>>1。然后判断,当low<=high成立时,若数组[mid]值大于key时,将数组下标的底值提高为mid+1,反之将高值降低为mid-1,如此,每次将搜索的范围减小一半,大幅提高搜索效率。
附图:
二分查找法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。