折半查找法（递归实现）

小甲鱼

题目：假设有数组 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

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

〤卐_vs_卍〤

小甲鱼，very good 加油:victory:

向往青莲

1. #include <stdio.h>
   
2. 
   
3. int bin_search(int *str, int n, int key)
   
4. {
   
5.     int m, low = 0, high = n-1;
   
6.     int mid = (low+high)/2;
   
7. 
   
8.      if ( str [mid] == key)
   
9.         return mid;
   
10.     if ( str[low] >= str[high])
    
11.         return -1;
    
12.     if ( str[mid] < key )
    
13.     {
    
14.         low = mid + 1;
    
15.         m = bin_search(&str[low], high-low+1, key);
    
16.     }
    
17.     if ( str[mid] > key )
    
18.     {
    
19.         high = mid - 1;
    
20.         m = bin_search(&str[low], high-low+1, key);
    
21.     }
    
22.     if ( -1 != m )
    
23.         m += low;
    
24. 
    
25.     return m;
    
26. }
    
27. 
    
28. int main(void)
    
29. {
    
30.     int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    
31.     int m,addr;
    
32. 
    
33.     printf("请输入待查找的关键字: ");
    
34.     scanf("%d", &m);
    
35. 
    
36.     addr = bin_search(str, 11, m);
    
37.     if ( -1 != addr )
    
38.     {
    
39.         printf("查找成功，可喜可贺，可口可乐! 关键字 %d 所在的位置是: %d\n", m, addr);
    
40.     }
    
41.     else
    
42.     {
    
43.             printf("查找失败!\n");
    
44.     }
    
45. 
    
46.     return 0;
    
47. }
    

复制代码

迷妮小子

我只是路过打酱油的。

diyawei

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

wo1988818chu

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. void BinSearch(int a[], int n, int search_val){
   
5.     int *low, *mid, *high;
   
6.     low = a;
   
7.     high = low + n;
   
8.     mid = low + (high - low)/2;
   
9. 
   
10.     if((*mid) > search_val)
    
11.         BinSearch(low, mid-low, search_val);
    
12.     if((*mid) < search_val)
    
13.         BinSearch(mid, high-mid, search_val);
    
14. 
    
15.     if((*mid) == search_val)
    
16.         printf("找到%d\n", search_val);
    
17.     if(mid == low)
    
18.         printf("找不到！");
    
19. }
    
20. 
    
21. 
    
22. int main()
    
23. {
    
24.     int a[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    
25.     BinSearch(a, 10, 55);
    
26.     return 0;
    
27. }

复制代码

704582254

1. #include<stdio.h>
   
2. int find(int a[11],int low,int high,int number)
   
3. {
   
4. int mid =(low+high)/2;
   
5. if (low>high)
   
6. {
   
7.         mid=-1;
   
8.         return mid;
   
9. }
   
10. if(a[mid]==number)
    
11. return mid+1;
    
12. else
    
13. {if(number<a[mid])
    
14. high =mid-1;
    
15. else
    
16. low  =mid+1;
    
17. find(a,low,high,number);
    
18. }
    
19. }
    
20. int main()
    
21. {
    
22.         int find(int a[11],int low,int high,int number);
    
23.         int number,low=0,high=10,findnumber;
    
24.         int a[11]={1,1,2,3,5,8,13,21,34,55,89};
    
25.         printf("please input a number:");
    
26.         scanf("%d",&number);
    
27.         if(number<a[0] || number > a[10])
    
28.         printf ("no find\n");
    
29.     else
    
30.         {
    
31.         findnumber=find(a,low,high,number);
    
32.         if(findnumber==-1)
    
33.     printf("no find\n");
    
34.         else
    
35.         printf("The number is %d\n",findnumber);
    
36.         }
    
37. }

复制代码

我自己写的

柠“萌”圆

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

                               
登录/注册后可看大图

1. #include <iostream>
   
2. 
   
3. int find(int arr[], int low, int high, int n) //使用折半查找法的函数要求被查找数组已被排序
   
4. {
   
5.     int mid = (high + low) / 2; // 找出数组中间元素的下标
   
6.     if (arr[mid] == n) // 如果找到数据,返回数据在数组中的位置,结束递归调用
   
7.         return mid;
   
8.     else if (mid == high || mid == low) // 如果数组中不存在该数据,返回-1
   
9.         return -1;
   
10.     else if (arr[mid] < n) // 如果中间元素小于被查找元素,则到数组后半段进行查找
    
11.         return find(arr, mid + 1, high, n);
    
12.     else // 如果中间元素大于被查找元素,则到数组前半段进行查找
    
13.         return find(arr, low, mid, n);
    
14. } // find函数也可以使用迭代实现
    
15. 
    
16. int main()
    
17. {
    
18.     int arr[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    
19.     int pos = find(arr, 0, 10, 55);
    
20.     std::cout << "55 = arr[" << pos << "]\n";
    
21.     pos = find(arr, 0, 10, 1);
    
22.     std::cout << "1 = arr[" << pos << "]\n"; //这里的pos = 1,说明如果数组中有重复元素折半查找法将查找下标值较大的元素
    
23.     return 0;
    
24. }

复制代码

这是我的

柠“萌”圆

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

                               
登录/注册后可看大图

我自己写的

你这段代码有错

じO-联合

真是难得给力的帖子啊。

抢地主

qiang li hzi chi lou zhu

沉默默

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

№靖

#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

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

707348125

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

zhangyj5566

强烈支持楼主ing……

我是桃川人

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

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

我是桃川人

1. /****************************************************************/
   
2. /************    查找元素是否在待查数据中      ****************/
   
3. /******************   利用折半查找法实现   ********************/
   
4. /***************** By Hellogz 2014.11.29 ***********************/
   
5. /***************************************************************/
   
6. #include <stdio.h>
   
7. #include <stdlib.h>
   
8. 
   
9. #define NUM     12      //数组的大小
   
10. 
    
11. //函数功能：查找某个元素是否在数组中
    
12. //参数 low：最低位下标
    
13. //参数 high：最高位下标
    
14. //参数 key：待查找的元素
    
15. //参数 str[]：被查找的数组
    
16. int found(int low, int high, int key, int str[])
    
17. {
    
18.     int mid;
    
19. 
    
20.     if (low > high)
    
21.     {
    
22.         return -1;
    
23.     }
    
24.     else
    
25.     {
    
26.         mid = (low + high) / 2;
    
27. 
    
28.         if (key == str[mid])
    
29.             return mid;
    
30.         if (key > str[mid])
    
31.             return found(mid + 1, high, key, str);
    
32.         if (key < str[mid])
    
33.             return found(low, mid - 1, key, str);
    
34.     }
    
35. }
    
36. 
    
37. int main()
    
38. {
    
39.     int str[NUM] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144};
    
40.     int n, addr;
    
41. 
    
42.     printf("请输入待查找的关键字:");
    
43.     scanf("%d", &n);
    
44. 
    
45.     addr = found(0, NUM -1, n, str);
    
46.     if (-1 != addr)
    
47.     {
    
48.         printf("\n查找成功，关键字 %d 所在的位置是：%d\n", n, addr);
    
49.     }
    
50.     else
    
51.     {
    
52.         printf("\n关键字 %d 不在列表中！\n", n);
    
53.     }
    
54. 
    
55.     system("pause");
    
56. 
    
57.     return 0;
    
58. }
    

复制代码

三个石头

很好