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

    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位置
    展开全文
  • 折半查找--当查找表是有序表时,可采用折半查找; 基本思想:在有序表中,取中间元素作为比较对象,若给定值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


    展开全文
  • NULL 博文链接:https://128kj.iteye.com/blog/1744446
  • Java二分查找实现,欢迎大家提出交流意见./***名称:BinarySearch*功能:实现了折半查找(二分查找)的递归和非递归算法.*说明:* 1、要求所查找的数组已有序,并且其中元素已实现Comparable接口,如Integer、String等.* 2、...

    Java二分查找实现,欢迎大家提出交流意见.

    /**

    *名称:BinarySearch

    *功能:实现了折半查找(二分查找)的递归和非递归算法.

    *说明:

    * 1、要求所查找的数组已有序,并且其中元素已实现Comparable接口,如Integer、String等.

    * 2、非递归查找使用search();,递归查找使用searchRecursively();

    *

    *本程序仅供编程学习参考

    *

    *@author: Winty

    *@date: 2008-8-11

    *@email: wintys@gmail.com

    */

    class BinarySearch> {

    private T[] data;//要排序的数据

    public BinarySearch(T[] data){

    this.data = data;

    }

    public int search(T key){

    int low;

    int high;

    int mid;

    if(data == null)

    return -1;

    low = 0;

    high = data.length - 1;

    while(low <= high){

    mid = (low + high) / 2;

    System.out.println("mid " + mid + " mid value:" + data[mid]);///

    if(key.compareTo(data[mid]) < 0){

    high = mid - 1;

    }else if(key.compareTo(data[mid]) > 0){

    low = mid + 1;

    }else if(key.compareTo(data[mid]) == 0){

    return mid;

    }

    }

    return -1;

    }

    private int doSearchRecursively(int low , int high , T key){

    int mid;

    int result;

    if(low <= high){

    mid = (low + high) / 2;

    result = key.compareTo(data[mid]);

    System.out.println("mid " + mid + " mid value:" + data[mid]);///

    if(result < 0){

    return doSearchRecursively(low , mid - 1 , key);

    }else if(result > 0){

    return doSearchRecursively(mid + 1 , high , key);

    }else if(result == 0){

    return mid;

    }

    }

    return -1;

    }

    public int searchRecursively(T key){

    if(data ==null)return -1;

    return doSearchRecursively(0 , data.length - 1 , key);

    }

    public static void main(String[] args){

    Integer[] data = {1 ,4 ,5 ,8 ,15 ,33 ,48 ,77 ,96};

    BinarySearch binSearch = new BinarySearch(data);

    //System.out.println("Key index:" + binSearch.search(33) );

    System.out.println("Key index:" + binSearch.searchRecursively(3) );

    //String [] dataStr = {"A" ,"C" ,"F" ,"J" ,"L" ,"N" ,"T"};

    //BinarySearch binSearch = new BinarySearch(dataStr);

    //System.out.println("Key index:" + binSearch.search("A") );

    }

    }

    本文出自 “天堂露珠” 博客,请务必保留此出处http://wintys.blog.51cto.com/425414/94051

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

    千次阅读 2015-06-16 09:27:53
    #include "stdio.h" int Bisearch(int a[],int low,int high,int k); int main() { int pos,s;... int a[10]={23,25,27,29,31,33,35,37,39,41};... printf("请输入你要查找的数\n");... printf("待查找的数
    #include "stdio.h"
    int Bisearch(int a[],int low,int high,int k);
    int main()
    {
    	int pos,s;
    	int a[10]={23,25,27,29,31,33,35,37,39,41};
    	printf("请输入你要查找的数\n");
    	scanf("%d",&s);
    	printf("待查找的数   %d\n",s);
    	pos=Bisearch(a,0,9,s);//参数传递弄错了,k和s。
    	if(pos==-1)
    		printf("没有找到该数\n");
    	else
    		printf("%d在数组中位置是%d\n",s,pos);
    	return 0;
    }
    
    /*int Bisearch(int a[],int low,int high,int k)
    {
    	int mid;
    	while(low<=high)
    	{
    	 mid=(low+high)/2;
    	 if(k==a[mid])return mid;
    	 else if(k<a[mid])high=mid-1;
    	 else low=mid+1;
    	}
    	return -1;
    	
    }*/
    
    
    int Bisearch(int a[],int low,int high,int k)
    {
    	int mid;
    	if(low>high)
    		return -1;
    	else
    	{
    		mid=(low+high)/2;
    		if(a[mid]==k)
    			return mid;
    		if(a[mid]<k)	
    			return Bisearch(a,mid+1,high,k);		
    		else
    			return Bisearch(a,low,mid-1,k);	
    	}
    	
    }
    


    函数调用参数之间关系还是把握不是太好。

    同时要分辨好数组下标值和数组值的区别。

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

    2018-05-23 13:24:41
    递归折半查找法基本的程序思想,初学者可以参考一下。
  • //因为在下次递归之中,传过去的已经当作bot,top else { cout mid endl ; return 0 ; } } else { printf ( "-1\n" ) ; //可能是因为头文件又stdio.h之类的? ...
  • 折半查找递归实现

    千次阅读 2017-05-06 21:09:31
    /** * 2017年4月19日18:01:27 * --------------------------------------------... * 折半查找算法递归实现 * ------------------------------------------------------ * 本程序的主要思路是: * data[]原始数据
  • 折半查找(BinarySearch)也称二分查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构, 而且表中元素按关键字有序排列。 查找过程: 从表的中间记录开始,如果给定值和中间记录的...
  • //请写出对有序表进行折半查找的非递归算法,并将对应的程序调试运行通过 #include #include #define N 100 typedef int Status; typedef int ElemType;typedef struct {//创建有序表 ElemType *list; int length;...
  • 折半查找法递归和非递归形式

    千次阅读 2015-06-01 11:30:15
    /* 1、折半查找的查找过程是:先确定待查记录所在区间,然后逐步缩小范围至到找到或者找不到该记录为止。...2、折半查找的性能分析可以由判定树得出,折半查找在查找成功时给定值进行比较的关键字个数至多为⌊log_2 ⌋
  • 折半查找法递归

    2015-01-19 13:59:43
    #include int bin_search(int num[],int low,int high,int key) { int mid; if(high >= low) { mid = (high+low)/2; if(num[mid] == key) { return mid; } else if(num[mid] > key) ... return
  • 递归算法 折半查找

    2021-07-10 19:59:25
    (一)递归算法 折半查找 BinarySearch(函数命名了解大驼峰命名 ) 目的 节省时间在一组有序数列中查找一个数。通过查找中间值进行不断比较。 代码如下: int BinarySEarch(int*a,/*数组*/,intx/*想要传入的数组*...
  • 二分查找法也称为折半查找法,它的思想是每次都与序列的中间元素进行比较。二分查找的一个前提条件是数组是有序的,假设数组array为递增序列,findData为要查找的数,n为数组长度,首先将n个元素分成个数大致相同的...
  • 1 import java.util.Scanner; 2 ... 4 * @author Administrator 递归算法折半查找 5 */ 6 public class zhebanchazhao_1 { 7 8 public static void main(String[] args) { 9 10 ...
  • 递归折半查找算法

    千次阅读 2019-02-19 10:02:08
    问题一:递归折半查找算法 注意:折半查找有一个条件,数据必须是有顺序性的,不然折半查找毫无意义; 原问题:有一数组A[10],里面存放了十个整数,顺序递增。任意输入一个n(位于数组里外均可),如果n数与数组...
  • 折半查找法介绍 在计算机科学中,折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。 搜索...
  • 【查找算法折半查找法

    千次阅读 2020-02-20 17:08:09
    本篇文章将介绍折半查找算法。 文章目录何为折半查找算法实现递归实现效率分析 何为折半查找? 上一篇文章介绍了顺序查找算法,我们知道,虽然顺序查找算法适用性高,但效率太低,那么能不能在此基础上继续提高...
  • 二分查找的递归算法折半查找

    千次阅读 2011-11-20 18:14:59
    #include int binarysearch(int a[], int low, int high, int x) {  int mid;  if (low > high)  return -1;  else  {  mid = (low + high) / 2;  if (x == a[mid]) ... else if (x
  • 原创作品,允许转载,转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任。... Java二分查找实现,欢迎大家提出...*功能:实现了折半查找(二分查找)的递归和非递归算法. *说明: * 1
  • Java算法折半查找法

    2020-04-26 10:43:49
    Java 算法折半查找法 算法介绍 折半查找法要求线性表是有序的,即表中记录按关键字有序(假设是递增有序的)。 折半查找的基本思路:设 R[low, ···, high] 是当前的查找区间,首先确定该区间的中间位置 mid = ...
  • 二分查找法(折半查找法):查找数组中是否包含指定元素。如果包含指定元素,则返回指定元素的index(从0开始);如果不包含指定元素,则返回-1; 前提:数组中的元素必须是有序的。 原理: 将被查找的数组分为...
  • 6-1、用递归折半查找(二分查找) 代码: int BinarySearch_(int* List, const int N, const int Left, const int Right) { if (Left <= Right) { int Mid = (Left + Right) / 2; // mid = 中间数 if (N &...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,305
精华内容 2,922
关键字:

折半查找法递归算法