折半查找法（递归实现）

小甲鱼 · 发表于 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

Message_Box · 发表于 2013-2-26 23:00:53

循环的问题全部可以转换为递归问题。

〤卐_vs_卍〤 · 发表于 2013-2-26 23:01:25

小甲鱼，very good 加油:victory:

向往青莲 · 发表于 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;
}

迷妮小子 · 发表于 2013-8-24 23:13:59

我只是路过打酱油的。

diyawei · 发表于 2013-10-6 15:52:42

穷死了没钱啊代码又下载不了了伤心

wo1988818chu · 发表于 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;
}

704582254 · 发表于 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);
        }
}

我自己写的

柠“萌”圆 · 发表于 2014-2-8 21:57:07

向往青莲发表于 2013-3-24 11:29

登录/注册后可看大图

#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;
}

这是我的

柠“萌”圆 · 发表于 2014-2-8 22:02:51

704582254 发表于 2014-1-24 16:39

登录/注册后可看大图

我自己写的

你这段代码有错

じO-联合 · 发表于 2014-2-17 22:05:29

真是难得给力的帖子啊。

抢地主 · 发表于 2014-3-29 15:48:30

qiang li hzi chi lou zhu

沉默默 · 发表于 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);
}

№靖 · 发表于 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;
}

zhuiyilx · 发表于 2014-9-20 04:35:46

求解答：那句if ( -1 != m )
m += low;
是什么意思？

707348125 · 发表于 2014-10-27 16:02:16

:sad好哈呀。。以后常来学习了

zhangyj5566 · 发表于 2014-11-16 21:52:26

强烈支持楼主ing……

我是桃川人 · 发表于 2014-11-29 21:09:41

zhuiyilx 发表于 2014-9-20 04:35
求解答：那句if ( -1 != m )
m += low;
是什么意思？

如果 m 不等 -1， m 等于 m 加 low；

我是桃川人 · 发表于 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;
}

三个石头 · 发表于 2015-7-18 21:55:43

很好

账号		自动登录	找回密码
密码			立即注册

[技术交流] 折半查找法（递归实现）

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