二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

前提:数组必须是有序的。

算法时间复杂度:O(log(n))

二分查找法也称为折半查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果xa[n/2],则我们只要在数组a的右 半部继续搜索x。

总之,二分查找算法的思想就跟二叉树的查找一样,如果大于就在右边找,小于就在左边找,等于就表示找到了。这里的结果我使用的是返回数组的下标,如果没有找到则返回-1。

//泛型方法

public static > int binarySearch(AnyType[]

anyType,AnyType any){

final int b = -1;

int low = 0,high = anyType.length;

if (keyanyType[high] || low > high) {

return b;

}

while(low <= high){

//int mid = (low+high)/2; //有溢出

//int mid = low + (high-low)/2; //无溢出

int mid = (low & high) + ((low ^ high) >> 1); //无溢出

if(anyType[mid].compareTo(any) > 0){

high = mid-1;

} else if(anyType[mid].compareTo(any) < 0){

low = mid+1;

} else {

return mid;

}

}

return b;

}

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

java heap buffer direct buffer_DirectByteBuffer内存释放讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。