公告:欢迎访问,查看更多资源请点我^.^!            点我关闭广告
二分法查找
2018-09-11 11:35:08
1196人阅读
评论(0)
分类:算法

    /**
* 二分法查找
* @param arr 从小到大排序的数组
* @param num 待查找数值
* @return 待查找数值在数组中的索引值,不存在返回-1
* @desc 二分法也叫折半查找,思路顾名思义
*/
private static int findNumber(int[] arr, int num) {
int min = 0, max = arr.length;
while (min <= max) {
int mid = (min + max) / 2;
if (arr[mid] < num) {
min = mid + 1;
} else if (arr[mid] > num) {
max = mid - 1;
} else {
return mid;
}
}
return -1;
} //测试

public static void main(String[] args) {

int size = 10000000;

/**
* 生成size个随机数组成数组
*/
long pStart = System.currentTimeMillis();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = new Random().nextInt(size);
}
long startS = System.currentTimeMillis();
System.out.println("生成数组耗时:" + (startS - pStart));
int num = arr[10]; //随便取一个数值用于查找

        // 排序算法详见 快速排序 ,切忌使用冒泡排序,否则就将数值改小一点
quickSort(arr, 0, arr.length); // 10000 - 3ms // 100000 - 35ms
long fStart = System.currentTimeMillis();
System.out.println("快速排序耗时:" + (fStart - startS));
int index = findNumber(arr, num);
System.out.println("查找耗时:" + (System.currentTimeMillis() - fStart));
System.out.println("查找结果:" + index + " 待查数值:" + num + " 验证:" + arr[index]);
}

最终结果可发现:索引和数值很相近,这是正常的,随机生成数字的概率使然!


分享一下:
赞一下(0)
博主资料
博主头像
zc521106
文章:34
浏览:19899
文章分类
Java(12)
NoSql(112)
数据库(12)
前端(12)
阅读排行
Java基础知识
(12)
NoSql应用
(112)
数据库Oracle语法
(12)
前端常用工具类
(12)
java web项目
(12)
linux安装mysql
(12)
评论区
这篇文章怎么样?写点评论吧!
姓名:
邮箱:
有回复时通知我:
发表
回复【10.20.30.32】:
暂无评论,快抢沙发!
* 以上用户言论只代表其个人观点,不代表iBlog网站的观点或立场,如有任何疑问请随时联系管理员...