鱼C论坛

 找回密码
 立即注册
查看: 13732|回复: 24

[技术交流] 折半查找法(递归实现)

[复制链接]
发表于 2013-2-26 22:59:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目:假设有数组 int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};

要求:用递归的方法实现折半查找法。

提示:折半查找法文字速成教程(http://bbs.fishc.com/thread-27964-1-1.html


视频讲解:http://blog.fishc.com/2214.html

源代码参考:http://bbs.fishc.com/thread-28077-1-1.html

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-2-26 23:00:53 | 显示全部楼层
循环的问题全部可以转换为递归问题。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2013-2-26 23:01:25 | 显示全部楼层
小甲鱼,very good 加油:victory:
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-3-24 11:29:46 | 显示全部楼层
#include <stdio.h>

int bin_search(int *str, int n, int key)
{
    int m, low = 0, high = n-1;
    int mid = (low+high)/2;

     if ( str [mid] == key)
        return mid;
    if ( str[low] >= str[high])
        return -1;
    if ( str[mid] < key )
    {
        low = mid + 1;
        m = bin_search(&str[low], high-low+1, key);
    }
    if ( str[mid] > key )
    {
        high = mid - 1;
        m = bin_search(&str[low], high-low+1, key);
    }
    if ( -1 != m )
        m += low;

    return m;
}

int main(void)
{
    int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    int m,addr;

    printf("请输入待查找的关键字: ");
    scanf("%d", &m);

    addr = bin_search(str, 11, m);
    if ( -1 != addr )
    {
        printf("查找成功,可喜可贺,可口可乐! 关键字 %d 所在的位置是: %d\n", m, addr);
    }
    else
    {
            printf("查找失败!\n");
    }

    return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2013-8-24 23:13:59 | 显示全部楼层
我只是路过打酱油的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-10-6 15:52:42 | 显示全部楼层
穷死了没钱啊 代码又下载不了了 伤心
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-12-24 23:17:38 | 显示全部楼层
#include <stdio.h>
#include <stdlib.h>

void BinSearch(int a[], int n, int search_val){
    int *low, *mid, *high;
    low = a;
    high = low + n;
    mid = low + (high - low)/2;

    if((*mid) > search_val)
        BinSearch(low, mid-low, search_val);
    if((*mid) < search_val)
        BinSearch(mid, high-mid, search_val);

    if((*mid) == search_val)
        printf("找到%d\n", search_val);
    if(mid == low)
        printf("找不到!");
}


int main()
{
    int a[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    BinSearch(a, 10, 55);
    return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-1-24 16:39:51 | 显示全部楼层
#include<stdio.h>
int find(int a[11],int low,int high,int number)
{
int mid =(low+high)/2;
if (low>high)
{ 
        mid=-1;
        return mid;
}
if(a[mid]==number)
return mid+1;
else
{if(number<a[mid])
 high =mid-1;
 else
 low  =mid+1;
 find(a,low,high,number);
} 
}
int main()
{
        int find(int a[11],int low,int high,int number);
        int number,low=0,high=10,findnumber;
        int a[11]={1,1,2,3,5,8,13,21,34,55,89};
        printf("please input a number:");
        scanf("%d",&number);
        if(number<a[0] || number > a[10])
        printf ("no find\n");
    else
        {
        findnumber=find(a,low,high,number);
        if(findnumber==-1)
    printf("no find\n");
        else 
        printf("The number is %d\n",findnumber);
        }
}
我自己写的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-2-8 21:57:07 | 显示全部楼层
#include <iostream>

int find(int arr[], int low, int high, int n) //使用折半查找法的函数要求被查找数组已被排序
{
    int mid = (high + low) / 2; // 找出数组中间元素的下标
    if (arr[mid] == n) // 如果找到数据,返回数据在数组中的位置,结束递归调用
        return mid;
    else if (mid == high || mid == low) // 如果数组中不存在该数据,返回-1
        return -1;
    else if (arr[mid] < n) // 如果中间元素小于被查找元素,则到数组后半段进行查找
        return find(arr, mid + 1, high, n);
    else // 如果中间元素大于被查找元素,则到数组前半段进行查找
        return find(arr, low, mid, n);
} // find函数也可以使用迭代实现

int main()
{
    int arr[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    int pos = find(arr, 0, 10, 55);
    std::cout << "55 = arr[" << pos << "]\n";
    pos = find(arr, 0, 10, 1);
    std::cout << "1 = arr[" << pos << "]\n"; //这里的pos = 1,说明如果数组中有重复元素折半查找法将查找下标值较大的元素
    return 0;
}
这是我的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-2-8 22:02:51 | 显示全部楼层

你这段代码有错
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-2-17 22:05:29 | 显示全部楼层
真是难得给力的帖子啊。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-3-29 15:48:30 | 显示全部楼层
qiang li hzi chi lou zhu
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-7-25 20:38:13 | 显示全部楼层
# include <stdio.h>

void search(int *, int, int, int);

int main(void)
{
        int a[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        search(a, 13, 0, 10);

        return 0;
}

void search(int * a, int val, int low, int hig)
{
        int mid = (low + hig) / 2;

        if ( low > hig ) {
                printf("search false!\n");
                return;
        }

        if ( a[mid] == val )
                printf("%d\n", mid + 1);
        else if ( a[mid] > val )
                search(a, val, low, mid-1);
        else
                search(a, val, mid + 1, hig);
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-9-12 16:32:41 | 显示全部楼层
#include <stdio.h>


int bin_search(int str[], int key, int low, int high)
{
        int mid = (low + high) / 2;

        if (low > high)
                return -1;
        if (str[mid] == key)
                return mid;
        if (str[mid] < key)
                low = mid + 1;
        if (str[mid] > key)
                high = mid - 1;
        bin_search(str, key, low, high);
}


int main()
{
        int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        int key, addr;

        printf("请输入待查找关键字:");
        scanf("%d", &key);

        addr = bin_search(str, key, 0, 10);

        if (-1 != addr)
        {
                printf("查找成功!关键字%d所在位置是:%d\n", key, addr + 1);
        }
        else
        {
                printf("查找失败!\n");
        }
        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2014-9-20 04:35:46 | 显示全部楼层
求解答:那句if ( -1 != m )
                    m += low;
是什么意思?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2014-10-27 16:02:16 | 显示全部楼层
:sad好哈呀。。以后常来学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-11-16 21:52:26 | 显示全部楼层
强烈支持楼主ing……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-11-29 21:09:41 | 显示全部楼层
zhuiyilx 发表于 2014-9-20 04:35
求解答:那句if ( -1 != m )
                    m += low;
是什么意思?

如果 m 不等 -1, m 等于 m 加 low;
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-11-29 21:10:15 | 显示全部楼层
/****************************************************************/
/************    查找元素是否在待查数据中      ****************/
/******************   利用折半查找法实现   ********************/
/***************** By Hellogz 2014.11.29 ***********************/
/***************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define NUM     12      //数组的大小

//函数功能:查找某个元素是否在数组中
//参数 low:最低位下标
//参数 high:最高位下标
//参数 key:待查找的元素
//参数 str[]:被查找的数组
int found(int low, int high, int key, int str[])
{
    int mid;

    if (low > high)
    {
        return -1;
    }
    else
    {
        mid = (low + high) / 2;

        if (key == str[mid])
            return mid;
        if (key > str[mid])
            return found(mid + 1, high, key, str);
        if (key < str[mid])
            return found(low, mid - 1, key, str);
    }
}

int main()
{
    int str[NUM] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144};
    int n, addr;

    printf("请输入待查找的关键字:");
    scanf("%d", &n);

    addr = found(0, NUM -1, n, str);
    if (-1 != addr)
    {
        printf("\n查找成功,关键字 %d 所在的位置是:%d\n", n, addr);
    }
    else
    {
        printf("\n关键字 %d 不在列表中!\n", n);
    }

    system("pause");

    return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-18 21:55:43 | 显示全部楼层
很好
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 04:01

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表