好久没写算法,写个二分查找练练手。。。
//recursive
int binarySearch_recursive(int *array,int lowInd ,int highInd,int searchValue){
int middleInd =(lowInd+highInd)/2;
if (lowInd<=highInd) {
if(array[middleInd]<searchValue){
//search in top half
lowInd = middleInd+1;
return binarySearch(array,lowInd,highInd,searchValue);
}else if(array[middleInd]>searchValue){
//search in low half
highInd = middleInd-1;
return binarySearch(array,lowInd,highInd,searchValue);
}else {
//find value
return middleInd;
}
}else{
return -1;
}
return -1;
}
//non recursive function()
int binarySearch_iterative(int *array,int length,int searchValue){
int low =0,high = length-1;
int middle =-1;
while (low<=high) {
middle =(low+high)/2;
if(array[middle]>searchValue){
high = middle-1;
}else if(array[middle]<searchValue){
low = middle+1;
}else {
//find value
return middle;
}
}
return -1;
}
分享到:
相关推荐
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
折半查找(也称为二分查找)是一种高效的查找算法,适用于有序数组。通过不断将查找区间对半分割,可以快速定位目标值的位置,时间复杂度为O(log n),其中n是数组长度。本文将详细介绍如何使用递归方法实现折半查找...
Java实现二分查找的递归和非递归算法
**折半查找(二分查找)算法** 折半查找,又称二分查找,是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两个部分,每次比较中间元素与目标值,根据比较结果缩小搜索范围。如果中间元素等于...
3. 设计容易:对于递归定义的问题或数据结构,设计递归算法可能比非递归算法更为简单。 递归的实现依赖于一个称为递归工作栈的数据结构。递归过程分为两部分: 1. 递推(Traversal):问题向更小的子问题推进,这个...
用C语言开发的递归和非递归二分查找算法,具体内容详见代码
在C++中,这两个实现可能分别对应于`二分查找递归代码.cpp`和`二分查找非递归代码.cpp`中的内容。在实际应用中,根据具体场景和性能需求,可以选择合适的实现方式。需要注意的是,二分查找的前提是输入数组必须是...
二分搜索,也被称为折半查找,是一种在...通过理解二分搜索的递归和非递归实现,我们可以更好地掌握分治策略,并将其应用到其他算法中,如快速排序、归并排序等。同时,这也是提升编程能力,理解和解决问题的重要步骤。
二分查找的空间复杂度主要取决于递归调用的深度,对于非递归版本,空间复杂度为O(1),因为它只需要常数级别的额外空间。递归版本的空间复杂度可能达到O(log n),因为每次递归调用都会占用栈空间。 **实验总结** 在...
本文将探讨递归算法中的一个重要应用——二分查找,并对比递归与非递归两种实现方式。 ##### 递归的概念介绍 递归是一种算法设计策略,它通过将问题分解成较小的子问题来解决问题。递归算法的特点在于函数调用自身...
C语言数据结构中二分查找递归非递归实现并分析 前言: 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高。因此较为受我们追捧。其实二分查找算法,是一个很经典的算法。但是呢,又容易写错。因为总是考虑...
总的来说,这个资源提供了Python3实现非递归二分查找的例子,以及相关的单元测试,帮助学习者理解并实践这一高效搜索算法。通过学习和应用这种算法,开发者可以更好地处理大数据集的搜索问题,提升代码的效率。同时...
快速排序(Quick Sort)与二分查找...综上所述,快速排序和二分查找是两种基础且实用的算法,它们的递归和非递归实现各有特点。理解并掌握这两种算法及其不同实现方式,对于提升编程技能和解决实际问题具有重要意义。
总的来说,通过这个实验,学生可以掌握分治算法的设计思路,了解二分查找的基本原理和实现方式,无论是非递归还是递归。此外,这个实验也强调了数据预处理的重要性,即在使用二分查找前需要确保数据已排序。通过编写...
折半查找,也称为二分查找,是一种在有序数组中搜索特定元素的高效算法。它主要利用了分治策略,将查找范围不断减半,直到找到目标元素或者确定元素不存在。这种算法通常在数据量较大且数据已排序的情况下使用,其...
在给定的Java代码中,提供了两种二分查找的实现方式:递归和非递归。 1. **递归实现**: 递归版本的二分查找在`binarySearch`函数中实现。其主要逻辑如下: - 如果目标值`m`小于中间元素`a[(low + high) / 2]`,...
二分查找是一种在有序数组中查找特定元素的高效算法,其基本思想是通过不断缩小搜索范围,快速定位目标值。在Java中实现二分查找,我们可以采用递归或非递归两种方式。以下是对这两种方法的详细介绍: 1. **递归...
《二分查找算法》是计算机科学中的一种经典算法,在本教学设计中,我们将深入探讨《二分查找算法》的教学目标、教学重点、教学难点、教学方法和教学过程。 教学目标 1. 了解二分查找算法的适用条件 2. 掌握二分...
在给定的代码中,提供了三种C语言实现二分查找的方法:递归和非递归。 1. **递归实现**: - `binSearch` 函数是递归版本的二分查找。它首先计算中间索引`mid`,然后根据`arr[mid]`与`key`的比较结果进行递归调用。...