`
128kj
  • 浏览: 601352 次
  • 来自: ...
社区版块
存档分类
最新评论

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

阅读更多
public class biSearch { 
 
    /**
     * @param args
     * 作者:undoner 
    /*
    折半查找--当查找表是有序表时,可采用折半查找;
    基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功;
    若给定值K小于中间记录的关键字,则在表的左半区继续查找;
    若给定值K大于中间记录的关键字,则在表的右半区继续查找,不断重复,直到查找成功/失败。
    */ 
 
    //折半查找非递归算法 
    //查询成功返回该对象的下标序号,失败时返回-1。 
    int BiSearch(int r[],int n,int k) 
    { 
        int low=0; 
        int high=n-1; 
        while(low<=high) 
        { 
            int mid=(low+high)/2; 
            if(r[mid]==k) 
                return mid; 
            else 
                if(r[mid]<k) 
                    low=mid+1; 
                else 
                    high=mid-1; 
        } 
        return -1; 
    } 
 
 
    //折半查找递归算法 
    //查询成功返回该对象的下标序号,失败时返回-1。 
    int BiSearch2(int r[],int low,int high,int k) 
    { 
        if(low<0) low=0;
        if(high>=r.length) high=r.length-1; //简单的参数验证
        if(low>high) 
            return -1; 
        else 
        { 
            int mid=(low+high)/2; 
            if(r[mid]==k) 
                return mid; 
            else 
                if(r[mid]<k) 
                    return BiSearch2(r,mid+1,high,k); 
                else 
                    return BiSearch2(r,low,mid-1,k); 
 
        } 
    } 
     
    public static void main(String[] args) { 
        biSearch bs=new biSearch(); 
        int r[]={1,2,3,4,5}; 
        System.out.println(bs.BiSearch(r,5,5)); 
        System.out.println(bs.BiSearch2(r,0,4,5)); 
        System.out.println(bs.BiSearch2(r,0,5,5)); 
    } 
 
}  
  


运行:
C:\java>java    biSearch
4
4
4
分享到:
评论

相关推荐

    折半查找的递归算法

    递归版本的折半查找算法与非递归版本的主要区别在于使用了函数调用自身的方式来实现查找区间对半分割的过程。递归版本通常更简洁,但可能会增加程序的调用栈开销。 #### 四、C语言实现 以下是一个使用C语言实现...

    非递归折半查找

    非递归查找的简单C语言程序,供初学者参考一下,哈哈。

    chazhao.rar_折半查找 递归算法

    下面是一个简单的折半查找递归算法的Python实现: ```python def binary_search_recursion(arr, target, low, high): if low &gt; high: return -1 # 查找失败,元素不存在 mid = (low + high) // 2 if arr[mid] =...

    Java代码递归的折半查找算法

    递归实现的折半查找相比于非递归实现,在代码结构上更为简洁、易于理解,但可能会因递归深度过深导致栈溢出的问题。 #### 核心代码解读 ##### 定义类 `BinarySearch` ```java package tes31; import java.util.*;...

    分别用递归和非递归方法实现二分查找算法 的完整程序

    分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。

    C语言-折半查找非递归

    C语言数据结构实验,在算法设计初级阶段也可以用到,入门级分享

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

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

    zhebanchazhao.rar_折半 查找_折半查找_折半查找算法_查找_查找算法

    - 非递归实现:虽然折半查找通常用循环实现,但也可以使用递归方式实现,使得代码更简洁易读。 - 完美平衡的二分查找:在某些情况下,如平衡二叉搜索树中,可以进一步优化查找效率,确保每个分支的元素数量接近。 - ...

    请写出对有序表进行折半查找的非递归算法.doc

    ### 对有序表进行折半查找的非递归算法 #### 非递归算法解析 在计算机科学领域,折半查找(又称二分查找)是一种高效的查找算法,它的工作原理是在一个有序数组中查找特定元素的位置。对于有序表进行折半查找的非...

    C语言实现顺序表的顺序查找和折半查找

    在上面的代码中,我们实现了两种折半查找算法:非递归算法和递归算法。在main函数中,我们首先输入数组的元素个数和数组元素,然后输入要查询的数,并使用BinSearch1或BinSearch2函数来查找该元素。 本文详细介绍了...

    java中折半法查找方法

    非递归实现的折半法查找算法可以使用以下步骤: 1. 初始化低位索引`low`和高位索引`high`,分别设置为数组的起始索引和结束索引。 2. 计算中点索引`mid`,即`low`和`high`的平均值。 3. 将目标值与中点值比较,如果...

    运用非递归方式设计折半查找法的程序.rar_折半查找

    【标题】:“运用非递归方式设计折半查找法的程序” 折半查找,也称为二分查找,是一种在有序数组中寻找特定元素的搜索算法。它的基本思想是每次将待搜索区域减半,直到找到目标元素或者确定目标元素不存在。这种...

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

    二分查找,也称为折半查找,是一种在有序数组中搜索特定元素的高效算法。它利用了数组的线性特性,每次将搜索范围减半,从而显著减少了查找次数。二分查找在计算机科学中有着广泛的应用,特别是在大量数据处理和...

    C++折半查找代码实现

    1. **非递归实现**: 可以尝试使用非递归的方式来实现折半查找,这样可以减少函数调用开销,提高效率。 2. **异常处理**: 增加异常处理机制,比如检查输入数组是否为空等。 3. **类型兼容性**: 进一步增强模板的类型...

    Java数据结构实现折半查找的算法过程解析

    2. 非递归调用:通过非递归调用实现折半查找,指定一个排好序的数组和要查找的值,同时指定左边界和右边界。在非递归调用过程中,通过while循环不断地缩小查找范围,直到找到目标元素或查找失败。 ```java static ...

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

    二分搜索,也被称为折半查找,是一种在有序数组中查找特定元素的高效算法。它主要利用了分治策略,将问题规模不断减半,从而快速定位目标值。本篇文章将详细探讨二分搜索的递归和非递归实现。 首先,我们来看递归...

    有关于折半查找的问题

    折半查找,也称为二分查找,是一种在有序数组中搜索特定元素的高效算法。它基于分治策略,每次将搜索区间减半,直到找到目标元素或者搜索区间为空。在这个问题中,描述提到元素是整型量,并且按从小到大的顺序排列,...

    折半查找及其改进算法及数据结构课程设计报告.doc

    2. 实现递归和非递归的折半查找算法。 3. 实现基于区间约束的改良折半查找算法。 4. 实现三分查找算法。 测试数据来自文件"in.txt",包含100个连续整数,从1到100。设计需针对不同大小的子序列(前50位和全部100位...

    数据结构实验报告-查找.doc

    本章实验报告主要围绕数据结构中的查找算法展开,通过三个实验题目,分别对线性表的顺序查找、折半查找(递归实现)和折半查找(非递归实现)进行了实验和分析。 一、线性表的顺序查找 本实验的主要目的是实现...

Global site tag (gtag.js) - Google Analytics