论坛 › 数据结构与算法 › 折半查找法（迭代实现）

浮云骑士 发表于 2015-11-15 16:19:58

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

int main()
{
       
        int str={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-18 15:10:07

/*
**折半查找法--迭代实现
**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 = {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)
                        low = middle + 1;
                else if(e < data)
                        high = middle - 1;
                else
                {
                        *index = middle;
                        return FIND;       
                }
                middle = (low + high) / 2;
        }
        if(e == data)
        {
                *index = middle;
                return FIND;       
        }
        else
                return NOTFIND;
}

圣狄雅哥 发表于 2018-2-3 16:59:05

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

不错不错

圣狄雅哥 发表于 2018-2-3 17:02:26

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

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

圣狄雅哥 发表于 2018-2-3 17:14:53

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

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

磨牙耗子 发表于 2018-4-22 09:49:16

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

Julia999 发表于 2019-1-30 10:04:42

I love FishC.com!

彭糖糖 发表于 2019-5-10 21:22:43

回复

kyrie_wx 发表于 2020-4-25 14:56:27

本帖最后由 kyrie_wx 于 2020-4-25 15:04 编辑

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

zhudesheng 发表于 2020-5-18 23:06:57

#include <stdio.h>

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


    if(value < (*str) || value > (*str)){
      return -1;
    }


    int mid = (end + start)/2;

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

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

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

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



int main(){

      int value,addr;
      int str = {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 发表于 2020-7-26 22:48:48

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

整形啊，str就是str

青衫烟雨客 发表于 2021-11-28 11:54:30

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

int search(int str[],int low,int high,int key)
{
    int mid;
    mid = (low+high)/2;
    if( str == key )
    {
      return mid;
    }
    else if( str < key )
    {
      if(low==high && str!=key)
      {
            return -1;
      }
      search(str,mid+1,high,key);
    }
    else if( str > key )
    {
      if(low==high && str!=key)
      {
         return -1;
      }
      search(str,low,mid-1,key);
    }
}
int main()
{
    int str = {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;
}

挽星 发表于 2022-4-21 18:18:03

用递归实现

#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 == k)
            return mid;
      else if (str > 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 = {1, 2, 3, 4, 5, 8, 13, 21};
    int n, i, addr;

    printf("数组的为！\n");
    for (i = 0; i < 8; i++)
    {
      printf("%d ", str);
    }
    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;
}

查看完整版本: 折半查找法（迭代实现）