当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

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

发表于: 2012-12-09   作者:128kj   来源:转载   浏览:
摘要: public class biSearch { /** * @param args * 作者:undoner /* 折半查找--当查找表是有序表时,可采用折半查找; 基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功; 若给定值K小于中间记录的关键字,则在表的左半区继续查找
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

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
代码部分: #include <stdio.h> #define MAXL 100 typedef int KeyType; typedef char InfoTy
/* * Copyright (c) 2015, 烟台大学计算机与控制工程学院 * All rights reserved. * 文件名称: mai
/* *Copyright (c) 2015, 烟台大学计算机与控制工程学院 *All rights reserved *作者:李宗政 *完成
/* * Copyright (c) 2015, 烟台大学计算机与控制工程学院 * All rights reserved. * 文件名称: mai
树结点的声明 struct BinaryNode { char element; BinaryNode* left; BinaryNode* right; BinaryNod
一:前言 二叉树的遍历方法分四种:前序,中序,后序以及层次遍历。 其中,前中后遍历方法的实现分递
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个
/* *第十四周(项目一)--数据结构-递归的折半查找 *Copyright (c) 2015 烟台大学计算机与控制工程
问题及代码: /* * 烟台大学计算机与控制工程学院 *文件名称:mian.cpp *作 者:刘磊 *完成日期:20
1.递归代码: #include<iostream> using namespace std; int common(int x , int y){ if(x ==
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号