折半查找法（迭代实现）

浮云骑士

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

#include<iostream>
using namespace std;

int bin_search( 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 )
        {
                bin_search( str, mid+1, high, key );
        }
        else if( str[mid] > key )
        {
                bin_search( str, low, mid-1, key );        
        }
        
}

int main()
{
        
        int str[11]={1,2,3,4,5,6,7,8,9,10,11};
        int add,n,low,high;
        
        low=0;
        high=11-1;
        
        cout<<"please input search number:";
        cin>>add;
        
        n = bin_search( str, low, high, add );
        
        cout<<"search success!"<<endl;
        cout<<"search number:"<<add<<" ,"<<"locate:"<<n<<endl;
        
        return 0;
}

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

千秋雪

/*
**折半查找法--迭代实现
**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]

青衫烟雨客

#include <stdio.h>
#include <stdlib.h>

int search(int str[],int low,int high,int key)
{
    int mid;
    mid = (low+high)/2;
    if( str[mid] == key )
    {
        return mid;
    }
    else if( str[mid] < key )
    {
        if(low==high && str[mid]!=key)
        {
            return -1;
        }
        search(str,mid+1,high,key);
    }
    else if( str[mid] > key )
    {
        if(low==high && str[mid]!=key)
        {
           return -1;
        }
        search(str,low,mid-1,key);
    }
}
int main()
{
    int str[11] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    int n,low,high,mid;
    printf("输入你要查找的关键字: ");
    scanf("%d",&n);
    low=0;
    high=10;
    mid=search(str,low,high,n);
    if(mid!=-1)
    {
        printf("查找的在数组的 %d 号元素",mid);
    }
    else
    {
        printf("查找不到！");
    }
    return 0;
}

挽星

用递归实现

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