`
kingbinchow
  • 浏览: 124600 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

二分查找的递归算法和非递归算法

阅读更多
好久没写算法,写个二分查找练练手。。。
//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实现二分查找的递归和非递归算法

    Java实现二分查找的递归和非递归算法

    折半查找的递归与非递归算法

    **折半查找(二分查找)算法** 折半查找,又称二分查找,是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两个部分,每次比较中间元素与目标值,根据比较结果缩小搜索范围。如果中间元素等于...

    递归算法和二分查找法

    3. 设计容易:对于递归定义的问题或数据结构,设计递归算法可能比非递归算法更为简单。 递归的实现依赖于一个称为递归工作栈的数据结构。递归过程分为两部分: 1. 递推(Traversal):问题向更小的子问题推进,这个...

    递归和非递归二分查找(C语言)

    用C语言开发的递归和非递归二分查找算法,具体内容详见代码

    折半(二分)查找的c++代码(递归和非递归)实现

    在C++中,这两个实现可能分别对应于`二分查找递归代码.cpp`和`二分查找非递归代码.cpp`中的内容。在实际应用中,根据具体场景和性能需求,可以选择合适的实现方式。需要注意的是,二分查找的前提是输入数组必须是...

    二分搜索的递归和非递归实现

    二分搜索,也被称为折半查找,是一种在...通过理解二分搜索的递归和非递归实现,我们可以更好地掌握分治策略,并将其应用到其他算法中,如快速排序、归并排序等。同时,这也是提升编程能力,理解和解决问题的重要步骤。

    计算机算法分析 二分查找 分治算法

    二分查找的空间复杂度主要取决于递归调用的深度,对于非递归版本,空间复杂度为O(1),因为它只需要常数级别的额外空间。递归版本的空间复杂度可能达到O(log n),因为每次递归调用都会占用栈空间。 **实验总结** 在...

    数据结构与算法(JAVA篇)之递归算法(二)

    本文将探讨递归算法中的一个重要应用——二分查找,并对比递归与非递归两种实现方式。 ##### 递归的概念介绍 递归是一种算法设计策略,它通过将问题分解成较小的子问题来解决问题。递归算法的特点在于函数调用自身...

    C语言数据结构中二分查找递归非递归实现并分析

    C语言数据结构中二分查找递归非递归实现并分析 前言: 二分查找在有序数列的查找过程中算法复杂度低,并且效率很高。因此较为受我们追捧。其实二分查找算法,是一个很经典的算法。但是呢,又容易写错。因为总是考虑...

    Python3实现非递归二分查找

    总的来说,这个资源提供了Python3实现非递归二分查找的例子,以及相关的单元测试,帮助学习者理解并实践这一高效搜索算法。通过学习和应用这种算法,开发者可以更好地处理大数据集的搜索问题,提升代码的效率。同时...

    快排与二分检索递归与非递归

    快速排序(Quick Sort)与二分查找...综上所述,快速排序和二分查找是两种基础且实用的算法,它们的递归和非递归实现各有特点。理解并掌握这两种算法及其不同实现方式,对于提升编程技能和解决实际问题具有重要意义。

    算法分析与设计-实验二 二分查找实验报告.docx

    总的来说,通过这个实验,学生可以掌握分治算法的设计思路,了解二分查找的基本原理和实现方式,无论是非递归还是递归。此外,这个实验也强调了数据预处理的重要性,即在使用二分查找前需要确保数据已排序。通过编写...

    chazhao.rar_折半查找 递归算法

    折半查找,也称为二分查找,是一种在有序数组中搜索特定元素的高效算法。它主要利用了分治策略,将查找范围不断减半,直到找到目标元素或者确定元素不存在。这种算法通常在数据量较大且数据已排序的情况下使用,其...

    二分查找算法

    在给定的Java代码中,提供了两种二分查找的实现方式:递归和非递归。 1. **递归实现**: 递归版本的二分查找在`binarySearch`函数中实现。其主要逻辑如下: - 如果目标值`m`小于中间元素`a[(low + high) / 2]`,...

    Java,二分查找,递归以及非递

    二分查找是一种在有序数组中查找特定元素的高效算法,其基本思想是通过不断缩小搜索范围,快速定位目标值。在Java中实现二分查找,我们可以采用递归或非递归两种方式。以下是对这两种方法的详细介绍: 1. **递归...

    《二分查找算法》完整版教学设计

    《二分查找算法》是计算机科学中的一种经典算法,在本教学设计中,我们将深入探讨《二分查找算法》的教学目标、教学重点、教学难点、教学方法和教学过程。 教学目标 1. 了解二分查找算法的适用条件 2. 掌握二分...

    C 二分查找 递归与非递归的实现代码

    在给定的代码中,提供了三种C语言实现二分查找的方法:递归和非递归。 1. **递归实现**: - `binSearch` 函数是递归版本的二分查找。它首先计算中间索引`mid`,然后根据`arr[mid]`与`key`的比较结果进行递归调用。...

Global site tag (gtag.js) - Google Analytics