以前工作过程中学习的过程中写了很多测试程序,上周acer本本硬盘坏了,换了个新硬盘,数据全部丢失了,很多有用的东西就这样没了,可惜的很。以后把工作和学习中的到的东西还是放到网上来比较好点。
最近,在论坛上看到有个人搞了个每日一题,觉得挺不错。最近在看数据结构,想想是否也可以来个每天看看数据结构。觉得那些东西虽然不是很难,但是若是坚持一段时间,量变必然会产生质变。而且每天花点时间在英语上,那么也会产生效果,背诵新概念的工程也该重启了,以前背了一段时间的,现在又忘了。
javaeye月刊上有一个关于24点算法的讨论,很多人也参入讨论,有人说看谁20行以内解决,似乎不可能,不过参入讨论给的代码都比我的要长很多,看来自己还不是太笨。数据机构不会每天都写,但是每天都会看点,过段时间把排序的多个方法总结下,希望09年有所提高。昨天写的个利用归并和递归来实现的排序,有些问题,在4个数的时候是正确的,多于四个数字的时候,有一个数字不正确,还没找到原因。先把学习的一个递归二分查找贴出来。
二分查找
int[] binary = {1,2,3,4,5,6,7,8,9};
int lower = 0;
int upper = binary.length-1;
int curIn;
int searchNum = 6;
while(true)
{
curIn = (upper + lower)/2;
if(binary[curIn] == searchNum)
{
System.out.println(searchNum + "存在于数组的" + curIn + "位置");
return;
}else if(upper < lower)
{
System.out.println(searchNum + "在数组中不存在");
return;
}else{
if(binary[curIn]>searchNum)
{
upper = curIn - 1;
}else if(binary[curIn]<searchNum)
{
lower = curIn + 1;
}
}
}
二分查找的递归实现,属于分治算法。分治算法, 常常是一个方法,这个方法中包含两个对自身的递归调用,但是只有一个真的执行了。
static int[] binary = {1,2,3,4,5,6,7,8,9};
public static void main(String[] args) {
int lower = 0;
int upper = binary.length;
int searchNum = 6;
binarySearch(searchNum,lower,upper);
}
private static void binarySearch(int searchNum, int lower, int upper) {
int curItem = (lower + upper)/2;
if(binary[curItem] == searchNum)
{
System.out.println(searchNum + "在数组的" + curItem + "位置上");
}else if(lower>upper)
{
System.out.println("不存在该值");
}
else
{
if(binary[curItem]>searchNum)
{
binarySearch(searchNum,lower,curItem-1);
}
if(binary[curItem]<searchNum)
{
binarySearch(searchNum,curItem+1,upper);
}
}
}
分享到:
相关推荐
分治法实现二分查找算法实现 分治法实现二分查找算法实现 分治法实现二分查找算法实现
二分查找基于分治算法的实现
二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
实现二分查找的完美算法 c++ 带有测试代码,和测试例子
用C++实现的二分搜索,改写了算法设计与分析课后的题目。按照《算法分析与设计》书上的例题的算法实现的。采用了分治法的思想。
分治法解决棋盘覆盖与二分查找问题,C++描述.算法设计与分析经典例题
二分查找,完整工程文件,源代码,VS2010
这个是二分检索的递归实现 具体的进去看看 有注释
安徽大学本科课程《算法设计与分析》实验二《二分查找算法BinarySearch》,包括.m文件和实验报告。
该word文档包含分治算法的思想,适用于用...经典实例(递归求累加,求阶乘、汉诺塔问题、快速排序算法、二分查找算法(折半查找算法)、归并排序算法、矩阵乘法和Strassen、大整数乘法、循环赛日程表)。 *无题目链接
折半查找法也称为二分查找法或二分搜索法,它充分利用了元素间的次序关系,采用分治策略而较快地查找数据。现要求给出一个待查找的实例,并给出二分搜索算法,编写程序利用此算法实现查找。
本资源包括一份分治法算法分析文档,4份Java源程序,包括二分查找、归并排序、快速排序、比赛日程安排。
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...
分治算法-二分查找 09 33.搜索旋转排序数组 分治算法-二分查找 19-2-22 10 53.最大子序和 分治算法 19-3-12 11 322.零钱兑换 动态规划 19-3-20 12 35.搜索插入位置 分治算法-二分查找 13 50.Pow(x, n) 分治算法-二分...
二分查找充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。 其基本原理是:首先,将目标元素与查找范围的中间值进行比较。如果目标元素等于中间值,则查找结束;如果目标元素...
常见的搜索算法包括线性搜索、二分搜索等。 图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是...
二分查找 归并排序 快速排序 穷举N位二进制 穷举所有排列
* 实现一个有序数组的二分查找算法* 实现模糊二分查找算法(比如大于等于给定值的第一个元素) ## 散列表* 实现一个基于链表法解决冲突问题的散列表* 实现一个LRU缓存淘汰算法 ## 字符串 ## 二叉树 ## 堆 ## 图 ##...
这次的二分查找算法实践,加深了我对二分法的理解。因为书本上有二分法查找的相关内容,我们没出现大问题。问题是出现在数组的定义上。我们一起找,没找到,最后上网查了一下才知道原来是我们数组定义的时候出了错!...
分治法排序 归并排序与二分查找 算法课课件