漫画:什么是二分查找?
The following article is from 程序员小灰 Author 蠢萌的小灰
脚本之家
你与百万开发者在一起
作者:蠢萌的小灰
本文由公众号程序员小灰(ID:chengxuyuanxiaohui)授权转载
————— 第二天 —————
什么意思呢?我们来举两个栗子:
给定一个有序数组
2,5,7,9,12,14,20,26,30
Case 1:
Case 2:
————————————
为什么说这样效率最高呢?因为每一次选择数字,无论偏大还是偏小,都可以让剩下的选择范围缩小一半。
给定范围0到1000的整数:
第一次我们选择500,发现偏大了,那么下一次的选择范围,就变成了1到499:
第二次我们选择250,发现还是偏大了,那么下一次的选择范围,就变成了1到249:
第三次我们选择125,发现偏小了,那么下一次的选择范围,就变成了126到249:
以此类推,最坏的情况需要猜测多少次呢?答案是 log1000 = 10次,也就是让原本的区间范围进行10次 “折半”。
刚才我们所分析的是猜数字的游戏。如果我们把场景转换成最初的面试问题:在包含1000个整型元素的有序数组中查找某个特定整数,又该如何去做呢?
同样道理,我们可以首先判断下标是499的元素(因为数组下标从0开始,到999结束),如果元素大于要查找的整数,我们再去判断下标是249的元素,然后判断下标124的元素......以此类推,直到最终找到想要的元素,或者选择范围等于0为止。
上述这个过程,就是所谓的二分查找算法,查找的时间复杂度是log(n)。
public static int binarySearch(int []array,int target){
//查找范围起点
int start=0;
//查找范围终点
int end=array.length-1;
//查找范围中位数
int mid;
//迭代进行二分查找
while(start<=end){
mid=(start+end)/2;
if(array[mid]==target){
return mid;
}else if(array[mid]<target){
start=mid+1;
}else{
end=mid-1;
}
}
return -1;
}
public static void main(String[] args) {
int[] array = new int[1000];
for(int i=0; i<1000;i++){
array[i] = i;
}
System.out.println(binarySearch(array, 173));
}
-END-
返回 上一级 搜索“Java 女程序员 大数据 留言送书 运维 算法 Chrome 黑客 Python JavaScript 人工智能 女朋友 MySQL 书籍 等关键词获取相关文章推荐。