public int binarySearch(int[] a, int searchKey) {
int lowerBound = 0;
int upperBound = a.length - 1;
int curIn;
while (true) {
curIn = (lowerBound + upperBound) / 2;
if (a[curIn] == searchKey)
return curIn;
else if (lowerBound > upperBound)
return -1;
else {
if (a[curIn] < searchKey)
lowerBound = curIn + 1;
else
upperBound = curIn - 1;
}
}
}
二分搜索的算法是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的key作比较,如果key=a[n/2]则找到x,算法终止。如果key<a [n/2],则我们只要在数组a的左半部继续搜索key(这里假设数组元素呈升序排列)。如果key>a[n/2],则我们只要在数组a的右半部继续搜索 key。
对于算法复杂度的比较:O(1) < O(logN) < O(N) < O(N^2)。
二分查找算法具有很高的效率,它的算法复杂度为O(lngN)。
分享到:
相关推荐
算法分析 二分搜索算法 实验报告 包含实验目的 试验分析和程序代码
用C语言动态实现二分搜索算法,可以清楚的看到算法之行的全部过程。
设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。
这是一个动态规划的二分搜索算法的程序 内容包括注释 及源代码 直接下载复制就可运行 其中还包含一个简易的数据生成器
大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法
二分搜索算法、快速排序,算法分析与设计(完整的代码,结合例题详细解析) 全套资源,求抱走!!! 1、给定数组a[0 : 8]={1, 8, 12, 15, 16, 21, 30, 35, 39}。采用二分搜索算法完成下述任务: 1)查找是否有元素30...
用java实现的二分搜索算法,能够同态的体现出搜索的过程
这是采用递归分治算法写的二分搜索算法, 是为上机考试准备的,呵呵呵
将优化二分搜索算法应用于全区视电阻率计算,以期提高计算精度和运算效率。以均匀全空间回线源中心的瞬变响应为基础,探讨全空间磁感应强度垂向分量Bz及其时间变化率Bz/T核函数曲线特征,推导晚期视电阻率表达式。...
请大家积极的来我这儿下载,本资源是对二分搜索算法的实现,java语言编写。大家要是觉得我的资源好,多来我家下载,有什么建议多提出来,大家共同进步。
本文档详细描述了算法分析与设计中,二分搜索算法的详尽解释,适合算法初学者。
数值算法课程:二分搜索算法+动态演示,C语言源码+flash开发的swf
设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时,I和j相同,均为x在数组中的位置。
二分搜索算法的实现,整合了冒泡排序,虽然用的是很常规的东西,但是是自己认真在做的,算是自己程序之路上的一个小小收获吧。
二分查找算法