首页 > 代码库 > 【算法数据结构Java实现】折半查找
【算法数据结构Java实现】折半查找
1.背景
以一个题目为例，一个整数x是一组按大小顺序排列好的数列中的一个数，我们要找到x在数列中的索引位置。
比如按从小到大排列的数列：
-3,-2,0,4,5,7,12,64
我们要找到数字7的位置，如果是线性查找，时间复杂度是O(n),如果用折半查找的话，时间复杂度是O(log(n))，因为每次折半，计算量少一半，所以取对数。
2.代码
package Algorithm_analysis;
public class Bisearch {
static int[] array={-3,-2,0,4,5,7,12,64};
public static void main(String args[]){
int left=0;
int right=array.length;
int center=0;
int k=7;
while(left<=right){
center=(right+left)/2;
if ((array[center]-k)==0){
System.out.print(center);
break;
}
else{
if((array[center]-k)>0){
right=center;
}
else{
left=center;
}
}
}
}
}
//输出结果7
/********************************
* 本文来自博客 “李博Garvin“
* 转载请标明出处:http://blog.csdn.net/buptgshengod
******************************************/
【算法数据结构Java实现】折半查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。