折半查找法（迭代实现）

浮云骑士

love_programe 发表于 2015-10-11 14:22
这个算法貌似就是那个所谓的“二分法”吧！！

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. int bin_search( int str[], int low, int high, int key )
   
5. {
   
6.         if( low > high )
   
7.         {
   
8.                 return -1;
   
9.         }
   
10.        
    
11.         int mid = ( low + high )/2;
    
12.        
    
13.         if( str[mid] == key )
    
14.         {
    
15.                 return mid;
    
16.         }
    
17.         else if( str[mid] < key )
    
18.         {
    
19.                 bin_search( str, mid+1, high, key );
    
20.         }
    
21.         else if( str[mid] > key )
    
22.         {
    
23.                 bin_search( str, low, mid-1, key );       
    
24.         }
    
25.        
    
26. }
    
27. 
    
28. int main()
    
29. {
    
30.        
    
31.         int str[11]={1,2,3,4,5,6,7,8,9,10,11};
    
32.         int add,n,low,high;
    
33.        
    
34.         low=0;
    
35.         high=11-1;
    
36.        
    
37.         cout<<"please input search number:";
    
38.         cin>>add;
    
39.        
    
40.         n = bin_search( str, low, high, add );
    
41.        
    
42.         cout<<"search success!"<<endl;
    
43.         cout<<"search number:"<<add<<" ,"<<"locate:"<<n<<endl;
    
44.        
    
45.         return 0;
    
46. }

复制代码

交个作业，有参考楼上的同学，勿怪！

千秋雪

/*
**折半查找法--迭代实现
**2016年9月17日 20:57:55
*/

//折半查找法的前提条件: 待查找的元素已经按顺序排列好
//设置3个指针, low, middle, high
//low指向查找区域的下界, high指向查找区域的上界, middle = (low + high) / 2

#include <stdio.h>

#define FIND 1
#define NOTFIND 0
#define SIZE 15            //数组的长度

typedef int Status;
typedef int ElemType;

Status half_search(ElemType *, ElemType, int *);     //待查找的数组, 需要查找的元素, 查找到的下标

int main()
{
        ElemType data[SIZE] = {1, 1, 2, 3, 5 ,8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
        ElemType e;                                    //元素按从小到大的顺序排列
        int index;
        printf("请输入要查找的元素:\n");
        scanf("%d", &e);
        if(half_search(data, e, &index))
                printf("查找成功! 元素%d在数组中的下标为%d\n", e, index);
        else
                printf("查找失败! 元素%d不在数组中\n", e);
        return 0;
}

//迭代查找法迭代实现
Status half_search(ElemType *data, ElemType e, int *index)
{
        int low, high, middle;
        low = 0;                           //初始化三个指针
        high = SIZE - 1;
        middle = (low + high) / 2;
        while(low != high)
        {
                if(e > data[middle])
                        low = middle + 1;
                else if(e < data[middle])
                        high = middle - 1;
                else
                {
                        *index = middle;
                        return FIND;       
                }
                middle = (low + high) / 2;
        }
        if(e == data[middle])
        {
                *index = middle;
                return FIND;       
        }
        else
                return NOTFIND;
}

圣狄雅哥

缘缘 发表于 2013-2-26 19:48
写了个递归的：

不错不错

圣狄雅哥

缘缘 发表于 2013-2-26 19:48
写了个递归的：

老哥红色部分应该是SIZE-1吧，或者你初始化设置11个数值
int flag = refind(data,0,SIZE,num);

圣狄雅哥

雪是梅之香 发表于 2015-1-19 10:29
现在才学习，附上我的代码：

这个写得比较准确，尤其是result=find(num,0,10,n)是10而不是11

磨牙耗子

大家很厉害，后来者精益求精

Julia999

I love FishC.com!

彭糖糖

回复

kyrie_wx

int HalfSearch( int str[], int low,int high, int key )
{
        if(low>high)
                return -1;
               
        int mid = (low+high)/2;
       
        if(str[mid] == key)
        {
                return mid;
        }
        else if(str[mid]<key)
        {
                HalfSearch(str,mid+1,high,key);
        }
        else if(str[mid]>key)
        {
                HalfSearch(str,low,mid-1,key);
        }
        else
        {
                return -1;
        }
       
}

zhudesheng

#include <stdio.h>

int binary_search(int (*str)[],int value,int start,int end){


    if(value < (*str)[start] || value > (*str)[end]){
        return -1;
    }


    int mid = (end + start)/2;

    if((*str)[mid] ==  value){
        return mid;
    }

    if(start ==  end){
        return -1;
    }

    if((*str)[mid] < value){
        return binary_search(str,value,mid+1,end);
    }

    if((*str)[mid] > value){
        return binary_search(str,value,start,mid-1);
    }
    return -1;
}



int main(){

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

        printf("请输入一个数字:");
        scanf("%d",&value);

        addr = binary_search(&str,value,0,10);
        if(addr != -1)
        {
            printf("%d 在str的%d\n",value,addr);

        }
        else
        {
            printf("%d 不在数组中!\n",value);
        }
        return 0;
}

807711012

YYB 发表于 2013-2-27 12:56
我有个问题，如果mid的值不是整数怎么弄啊？比如LOW = 0 High = 9，MID =4.5 这个时候怎么办啊？str[4.5]不 ...

整形啊，str[4.5]就是str[4]

青衫烟雨客

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int search(int str[],int low,int high,int key)
   
5. {
   
6.     int mid;
   
7.     mid = (low+high)/2;
   
8.     if( str[mid] == key )
   
9.     {
   
10.         return mid;
    
11.     }
    
12.     else if( str[mid] < key )
    
13.     {
    
14.         if(low==high && str[mid]!=key)
    
15.         {
    
16.             return -1;
    
17.         }
    
18.         search(str,mid+1,high,key);
    
19.     }
    
20.     else if( str[mid] > key )
    
21.     {
    
22.         if(low==high && str[mid]!=key)
    
23.         {
    
24.            return -1;
    
25.         }
    
26.         search(str,low,mid-1,key);
    
27.     }
    
28. }
    
29. int main()
    
30. {
    
31.     int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    
32.     int n,low,high,mid;
    
33.     printf("输入你要查找的关键字: ");
    
34.     scanf("%d",&n);
    
35.     low=0;
    
36.     high=10;
    
37.     mid=search(str,low,high,n);
    
38.     if(mid!=-1)
    
39.     {
    
40.         printf("查找的在数组的 %d 号元素",mid);
    
41.     }
    
42.     else
    
43.     {
    
44.         printf("查找不到！");
    
45.     }
    
46.     return 0;
    
47. }

复制代码

挽星

用递归实现

#include <stdio.h>

int binary_search(int str[], int low, int high, int k)
{
    int mid;
    if (low <= high)
    {
        mid = (low + high) / 2;
        if (str[mid] == k)
            return mid;
        else if (str[mid] > k)
        {
            return binary_search(str, mid - 1, low, k);
        }
        else
        {
            return binary_search(str, mid + 1, high, k);
        }
    }
    else
        return 0;
}

int main()
{
    int str[8] = {1, 2, 3, 4, 5, 8, 13, 21};
    int n, i, addr;

    printf("数组的为！\n");
    for (i = 0; i < 8; i++)
    {
        printf("%d ", str[i]);
    }
    printf("\n");
    printf("请输入待查找的关键字：");
    scanf("%d", &n);

    addr = binary_search(str, 0, 7, n);
    if (-1 != addr)
    {
        printf("查找成功，关键字%d所在的位置为%d\n", n, addr + 1);
    }
    else
    {
        printf("查找失败！\n");
    }

    return 0;
}