二分搜索有两种常见的实现方法:递归实现、迭代实现。其中递归实现的代码量是最少的(但计算机执行的代码却很多哦)。
public static int binarySearch(int a[], int x, int left, int right) {
if (left > right) {
return -1;
} else {
int mid = (left + right) / 2;
if (x == a[mid]) {
return mid;
}
if (x > a[mid]) {
return binarySearch(a, x, mid + 1, right);//***
} else {
return binarySearch(a, x, left, mid);//***
}
}
}
代码中有注释***的两句就是递归调用啦!我任然记得:老师说每届学生都纠结于这两句里的return能不能删掉。我的理解是:binarySearch是一个有返回值的函数。这就会有两个要求:1、执行该函数时,得保证它有返回值;2、调用该函数时,一般要有个与它返回值类型相同类型的变量接收它(有些时候返回值就是一个标识,这种情况除外)。
显然要求2可以说明问题了,但对于正在纠结的人可能说服力不是那么大。那么,就请继续仔细看看代码会如何执行。
public static int binarySearch(int a[], int x, int left, int right) {
if (left > right) {
return -1;
} else {
int mid = (left + right) / 2;
if (x == a[mid]) {
return mid;
}
if (x > a[mid]) {
binarySearch(a, x, mid + 1, right);//***
} else {
binarySearch(a, x, left, mid);//***
}
// ***statement ***
}
}
我们清楚这个递归不会是死递归,在最后一次调用(假设为第N次调用)中,return -1; 或return mid; 会被执行。这样回到了第 N-1 次调用的函数体,代码接着往下执行到 ***statement*** 接着第 N-1 次调用走完了。恍然大悟,这次调用是没有返回值的。
至此,道理讲明了。作为个人学习,顺便贴上些其它的实现代码。
public static int BinarySearch(int[] array, int key)
{
int low = 0;
int high = array.Length - 1;
int middle = 0;
while (low <= high)
{
middle = (low + high) / 2;
int middleValue = array[middle];
if (middleValue < key)
{
low = middle + 1;
}
else if (middleValue > key)
{
high = middle - 1;
}
else
{
return middle;
}
}
return -(low + 1);
}
此代码来自CSDN博客:http://blog.csdn.net/xzjxylophone/archive/2009/10/23/4714326.aspx
public static int BinarySearchIteration(int[] array, int key)
{
int low = 0;
int high = array.Length - 1;
int middle = 0;
while (low < high)
{
middle = (low + high) / 2;
if (key > array[middle])
{
low = middle + 1;
}
else
{
high = middle;
}
}
if (low > high)
{
return -1;
}
else
{
if (key == array[low])
{
return low;
}
else
{
return -1;
}
}
}
本代码来自CSDN博客:http://blog.csdn.net/xzjxylophone/archive/2009/10/23/4714326.aspx
分享到:
相关推荐
二分搜索的递归和非递归实现。比较简单的实现。
这个是二分检索的递归实现 具体的进去看看 有注释
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
深度搜索+递归实现银行家算法安全序列全搜索算法实现代码.doc
自己写的用递归实现的背包问题,欢迎各位高手指正。
//二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则返回-1; int mid=(low+high)/2; if(low>high){ return -1;//该元素不...
二分查找的递归与非递归实现(java版)
Java二分查找递归算法
这里本人自己写的是折半查找算法(又称二分查找)的c++代码的实现, 用的是递归的方法和非递归的方法, 里面的代码已经编译通过,并且优化好, 有需要的朋友可以下载借鉴一下
本资源是数据结构中利用非递归法实现n皇后问题的一个C++代码,仅供参考,欢迎指正
快速选择非递归与递归算法实现
linux 目录树实现代码,使用的是递归的算法
最近不少面试问到格雷码的递归问题,写了个用递归方式实现格N位雷码的产生于输出,程序代码量很少,可以直接运行。可以下载看看。
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
快排与二分检索的递归与非递归算法分析与设计
二分检索的递归实现:这里使用的是JUnit单元测试方法,利用断言进行样例测试,结果显示3个样例全部通过。
用C语言开发的递归和非递归二分查找算法,具体内容详见代码
主要介绍了Python基于递归算法实现的走迷宫问题,结合迷宫问题简单分析了Python递归算法的定义与使用技巧,需要的朋友可以参考下
ackman函数的递归和非递归,学习数据结构的素材,非递归是使用堆栈实现的。
这是采用递归分治算法写的二分搜索算法, 是为上机考试准备的,呵呵呵