折半查找法（递归实现）,数据结构与算法,技术交流,鱼C论坛

小甲鱼 发表于 2013-2-26 22:59:32

折半查找法（递归实现）

题目：假设有数组 int str = {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 == key)
   return mid;
if ( str >= str)
   return -1;
if ( str < key )
{
   low = mid + 1;
   m = bin_search(&str, high-low+1, key);
}
if ( str > key )
{
   high = mid - 1;
   m = bin_search(&str, high-low+1, key);
}
if ( -1 != m )
   m += low;

return m;
}

int main(void)
{
int str = {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 = {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,int low,int high,int number)
{
int mid =(low+high)/2;
if (low>high)
{
mid=-1;
return mid;
}
if(a==number)
return mid+1;
else
{if(number<a)
high =mid-1;
else
low=mid+1;
find(a,low,high,number);
}
}
int main()
{
int find(int a,int low,int high,int number);
int number,low=0,high=10,findnumber;
int a={1,1,2,3,5,8,13,21,34,55,89};
printf("please input a number:");
scanf("%d",&number);
if(number<a || number > a)
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 static/image/common/back.gif

#include <iostream>

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

int main()
{
int arr = {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 static/image/common/back.gif
我自己写的

你这段代码有错

じ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 = {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 == val )
printf("%d\n", mid + 1);
else if ( a > 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 == key)
return mid;
if (str < key)
low = mid + 1;
if (str > key)
high = mid - 1;
bin_search(str, key, low, high);
}

int main()
{
int str = {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)
         return mid;
   if (key > str)
         return found(mid + 1, high, key, str);
   if (key < str)
         return found(low, mid - 1, key, str);
}
}

int main()
{
int str = {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

很好

页: [1] 2

鱼C论坛's Archiver

折半查找法（递归实现）