精华内容
下载资源
问答
  • 折半查找递归算法

    2015-11-02 09:54:24
    折半查找递归算法,非常实用,可以实现的C语言程序
  • java 折半查找递归算法 递归算法

    千次阅读 2017-05-20 11:13:49
    package datastruct.find; public class Binary... //方法一:非递归折半查找: private static void binarySearch(int a[],int k) { int low=0; int high=a.length-1; int mid; while (low) { mid=
    package datastruct.find;
    
    public class BinarySearch {
    	//方法一:非递归折半查找:
    	private static void binarySearch(int a[],int k) {
    		int low=0;
    		int high=a.length-1;
    		int mid;
    		while (low<=high) {  
    			mid=(low+high)/2;
    			if (k==a[mid]) {
    				System.out.println(a[mid]+"在"+mid+"位置");
    			     return;
    			}else {
    				if (k<a[mid]) {
    					high=mid-1;
    				}
    				else {
    					low=mid+1;
    				}
    			}
    		}
    		System.out.println("无法查找到该元素!");
    	}
    	//方法二:使用递归的折半查找
    	private static int binarySearch(int a[],int k,int low,int high ) {
    		if (a.length<=0) {
    			System.out.println("数组内元素为空!");
    			return -1;
    		} 
    		if (low>high) {
    			System.out.println("无法查找到该元素!");
    			return -1;
    		}else {
    			int mid=(low+high)/2;
    			if (k==a[mid]) {
    				System.out.println(a[mid]+"在"+mid+"位置");
    			     return mid;
    			}else {
    				if (k<a[mid]) {
    				 return	binarySearch(a, k, low, mid-1);
    				}else {
    				 return binarySearch(a, k, mid+1, high);
    				}
    			}
         	}
    	}
    	
    	
         public static void main(String[] args) {
    		int a[]={1,2,3,4,5,6,7};
    		System.out.println("非递归算法:");
    		binarySearch(a, 1);
    		binarySearch(a, 2);
    		binarySearch(a, 3);
    		binarySearch(a, 4);
    		binarySearch(a, 5);
    		binarySearch(a, 6);
    		binarySearch(a, 7);
    		System.out.println("递归算法:");
    		binarySearch(a, 1, 0, a.length-1);
    		binarySearch(a, 2, 0, a.length-1);
    		binarySearch(a, 3, 0, a.length-1);
    		binarySearch(a, 4, 0, a.length-1);
    		binarySearch(a, 5, 0, a.length-1);
    		binarySearch(a, 6, 0, a.length-1);
    		binarySearch(a, 7, 0, a.length-1);
    	}
    }


    运行结果:
                     非递归算法:
                     1在0位置
                     2在1位置
                     3在2位置
                     4在3位置
                     5在4位置
                     6在5位置
                     7在6位置
                     递归算法:
                     1在0位置
                     2在1位置
                     3在2位置
                     4在3位置
                     5在4位置
                     6在5位置
                     7在6位置
    展开全文
  • 题目:写出折半查找递归算法。初始调用时,low为1,high为ST.Length 关键字: 折半查找递归算法 思路: 根据查找的起始位置和终止位置,将查找序列一分为二,判断所查找的关键字在哪一部分,然后用新的序列的...

    题目:写出折半查找的递归算法。初始调用时,low为1,high为ST.Length

    关键字: 折半查找,递归算法

    思路:
    根据查找的起始位置和终止位置,将查找序列一分为二,判断所查找的关键字在哪一部分,然后用新的序列的起始位置和终止位置递归求解。
    首先,确定所需变量
    查找表ST,查找目标key,查找起始位置low 和查找终止位置high
    (因为本题使用递归算法,说明查找的起始位置和终止位置一直在递归变化,所以需要设为变量)

    其次,设计递归出口
    即查找结束的情况:
    1.查找失败的条件:low>high
    2.查找成功的条件:ST.mid==key

    分析: 算法把规模为n的复杂问题经过多次递归调用转化为规模减半的子问题求解。
    时间复杂度为O(log2 n,)
    算法中用到了一个递归工作栈,其规模与递归深度有关,也是O(log2 n)

    代码:

    typedef struct{
        ElemType *elem;
        int length;
    }SSTable;
    int BinSearchRec(SSTable ST,ElemType key,int low,int high){//在有序表中递归折半查找其关键字为key的元素,返回其在表中序号
        if (low>high)//查找失败,key不在查找表中
           return 0;
        mid=(low+high)/2;//取中间位置
        if(key>ST.elem[mid])//向后半部分查找
           BinSearchRec(ST,key,mid+1;high);
        else if(key<ST.elem[mid])//向前半部分查找
           BinSearchRec(ST,key,low,mid-1);
        else //查找成功
            return mid;   
    }
    
    展开全文
  • 折半查找--当查找表是有序表时,可采用折半查找; 基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功; 若给定值K小于中间记录的关键字,则在表的左半区继续查找; ...
    package Ceshi;
    
    public class biSearch {
    
    	/**
    	 * @param args
    	 */
    	/*
    	折半查找--当查找表是有序表时,可采用折半查找;
    	基本思想:在有序表中,取中间元素作为比较对象,若给定值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>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,1,5,5));
    	}
    
    }
    

     

    文献来源:

    UNDONER(小杰博客) http://blog.csdn.net/undoner

    LSOFT.CN(琅软中国) http://www.lsoft.cn


     

    展开全文
  • 折半查找递归算法和非递归

    千次阅读 2016-11-24 19:19:56
    设计一个算法,实现折半查找,很简单的问题。在这里列举下递归和非递归 递归实现 #include #include #include #include #include #include #include using namespace std; int n,a[105]; int Search_Bin...

    设计一个算法,实现折半查找,很简单的问题。在这里列举下递归和非递归

    递归实现

    #include <iostream>
    #include <cstdio>
    #include <ctime>
    #include <cstdlib>
    #include <stack>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    int n,a[105];
    
    int Search_Bin(int stat,int end,int tmp)
    {
    	int i,j;
    	
    	if(stat>end)
    		return -1;
    	if(stat==end)
    	{
    		return stat;
    	}
    	
    	if(tmp==a[(stat+end)/2])
    	{
    		return (stat+end)/2;
    	}
    	if(tmp>a[(stat+end)/2])
    	{
    		return Search_Bin((stat+end)/2+1,end,tmp);
    	}
    	else if (tmp<a[(stat+end)/2])
    	{
    		return Search_Bin(stat,(stat+end)/2-1,tmp);
    	}
    }
    
    int main()
    {
    	int i,j,tmp;
    	
    	printf("请输入你要随机产生的数的个数\n");	
    	scanf("%d",&n);
    	srand(time(0));
    	for(i=0;i<n;i++)
    	{
    		a[i]=rand()%1000;
    	}
    	sort(a,a+n);
    	printf("随机产生的数排序后的answer是\n");
    	for(i=0;i<n;i++)
    	{
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    	printf("请输入你要查找的数\n");
    	scanf("%d",&tmp);
    	printf("该数所在的位置是%d个\n",Search_Bin(0,n-1,tmp)+1);
    	
    	return 0;
    }

    非递归实现

    #include <iostream>
    #include <cstdio>
    #include <ctime>
    #include <cstdlib>
    #include <stack>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    int n,a[105];
    
    int Search_Bin(int stat,int end,int tmp)
    {
    	int i,j;
    	
    	printf("该数所在的位置是");
    	while(stat<=end)
    	{
    		if(stat==end)
    		{
    			printf("%d\n",stat+1);
    			break;
    		}
    		
    		if(tmp==a[(stat+end)/2])
    		{
    			printf("%d\n",stat+1);
    			break;
    		}
    		if(tmp>a[(stat+end)/2])
    			stat=(stat+end)/2+1;
    		else if(tmp<a[(stat+end)/2])
    			end=(stat+end)/2-1;
    	}
    	
    }
    
    int main()
    {
    	int i,j,tmp;
    	
    	printf("请输入你要随机产生的数的个数\n");	
    	scanf("%d",&n);
    	srand(time(0));
    	for(i=0;i<n;i++)
    	{
    		a[i]=rand()%1000;
    	}
    	sort(a,a+n);
    	printf("随机产生的数排序后的answer是\n");
    	for(i=0;i<n;i++)
    	{
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    	printf("请输入你要查找的数\n");
    	scanf("%d",&tmp);
    	Search_Bin(0,n-1,tmp)+1;
    	//printf("该数所在的位置是%d个\n",Search_Bin(0,n-1,tmp)+1);
    	
    	return 0;
    }


    展开全文
  • 算法思想:从表的一端开始,依次将记录的关键字和给定值进行比较,若某个记录的关键字和给定的值相等,则查找成功;反之,若扫描整个表后,仍未找到关键字和给定值相等的记录,则查找失败。 int seqsearch(seqlist...
  • Java二分查找实现,欢迎大家提出交流意见./***名称:BinarySearch*功能:实现了折半查找(二分查找)的递归和非递归算法.*说明:* 1、要求所查找的数组已有序,并且其中元素已实现Comparable接口,如Integer、String等.* 2、...
  • 折半查找的递归与非递归算法

    千次阅读 2018-08-07 09:43:35
    //折半查找只能用于有序的顺序表 public class BinarySearch {  //递归算法  public static int binaryDiGuiSearch(int[] data,int low,int high,int x) {  if(low&gt;high){  return -1;  ...
  • //a[]是数组,n是数组长度,key是查找的关键字 int BinSearch(int a[],int n,int key) { int l=0,r=n-1; int mid; while(l<=r){ mid=(1+r)/2; if(a[mid]==key) return mid; else if(a[mid]<key) l=...
  • 有序表折半查找递归算法

    千次阅读 2017-11-16 20:33:55
    #include #include typedef struct{ int key; }Elemtype; typedef struct{ Elemtype *elem; int length; }Table; int Create(Table &S,int n){ S.elem=(Elemtype *)malloc(n*sizeof(Elemtype));...S.elem){
  • 回家翻了翻之前做的C语言基础笔记,发现居然还穿插了几个算法,本着一步一个脚印的原则,今天就针对笔记里面的第一个查找算法折半查找(也叫二分查找),通过自己的实验,网络资料等,进行了学习和研究,同时也...
  • 递归折半查找算法

    千次阅读 2019-02-19 10:02:08
    问题一:递归折半查找算法 注意:折半查找有一个条件,数据必须是有顺序性的,不然折半查找毫无意义; 原问题:有一数组A[10],里面存放了十个整数,顺序递增。任意输入一个n(位于数组里外均可),如果n数与数组...
  • //递归 int BinarySearch(int arr[],int n,int left, int right) { if (left ) { int middle = left + (right - left)/2; //防溢出 if (n == arr[middle]) { return middle; } else i
  • 递归算法 折半查找

    2021-07-10 19:59:25
    (一)递归算法 折半查找 BinarySearch(函数命名了解大驼峰命名 法) 目的 节省时间在一组有序数列中查找一个数。通过查找中间值进行不断比较。 代码如下: int BinarySEarch(int*a,/*数组*/,intx/*想要传入的数组*...
  • [code="... 折半查找--当查找表是有序表时,可采用折半查找; 基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功; 若给定值K小于中间记录的关键...
  • } int seek(ST S) //二分查找递归 { int low, high,mod; printf("查询数字:"); scanf_s("%d",&key); low = 1; high = S.length; while (high >= low) { mod = (low + high) / 2; if (key == S.a[mod]) ...
  • All rights reserved. 文件名称:text.cpp 作者:黄潇慧 完成日期:2017年11月27日 版本:vc6.0 问题描述: ...折半查找: main.c#include #define MAXL 100 typedef int KeyType; ty

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,066
精华内容 4,826
关键字:

折半查找的递归算法