• 新记

    • C++折半查找法

    #include <iostream>
    using namespace std;
    int main( )
    {
    int a[15]={20,19,16,15,14,13,12,10,9,7,6,5,3,2,1};
    int max,min,mid,x,i,n;
    min=1,max=20,mid=20;n=0;
    cout<<"please input a number: ";
    cin>>x;
    for(;min<=max;)
    {
    if(x==mid)
    {
    for(i=0;i<15;i++)
    {if(a[i]>x) n=n+1;}
    cout<<"此数为第 "<<n+1<<"个元素的值"<<endl;break;}
    mid=(min+max)/2;
    if(x<mid) max=mid-1;
    if (x>mid) min=mid+1;}
    if (x!=mid) cout<<"无此数"<<endl;
    return 0;}

    这个是我码的，不过似乎有个BUG，就是输入4、8、11等之内的数时还是显示有此数而且有说第几个，是他后面的那个数。比如11就是显示第8个，而第8个数其实是10……
    怎么改……

    举报该文章
    相关建议   2017-06-19

    折半查找法是算法一种，可以被任何计算机语言使用。用C语言自然也可以实现。

    1、定义：

    在计算机科学中，折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

    搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

    2、查找规则：

    折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。

    3、C语言参考代码：

    int bin_search(int A[],int n,int key){
    //在长度为n的数组A ä¸­æŠ˜åŠæŸ¥æ‰¾å€¼ä¸ºkey的元素，并返回下标值。如果不存在则返回-1.
        int low,high,mid;
        low = 0;
        high = n-1;//初始low和high为数组的两端。
        while(low<=high)
        {
            mid =(low + high)/2;//查找中心点。
            if(A[mid]==key)return mid;//已找到，返回下标值。
            if(A[mid]<key){//中点位置比key值小，以mid+1为新的下限值。
                low =mid + 1;
            }
            if(A[mid]>key){//中点位置比key值大，以mid-1为新的上限值。
                high= mid - 1;
            }
        }
        return -1;//未找到，返回-1.
    }
    温馨提示：内容为网友见解，仅供参考
    其他看法
    第1个回答  推荐于2018-05-10

    你对对半查找理解错了，你的min,max应该是下标而不是值


    原理：类似于二分法解方程，二分查找首先比对序列中间的数是否是要找的数，如果不是，由于是有序数列，则看其在左侧区间还是右侧区间，舍弃不在的那一半区间，然后在剩余的区间重复刚才的办法，直到找到该数，由于每次舍弃一半的数据量，所以查找效率较高。


    描述：设三个变量 left,right,middle分别为序列的两侧下标和中间下标，当判断出不在左侧区间，则 left=middle+1 ，从而利用右侧一半构造出一个新区间，否则 right=middle-1，利用左边一侧构造新区间，然后重复刚才过程，如此下去，要么找到数据，要么left>right，此时也应该停止查找，说明序列中没有该数。


    const int N=10;
     int left,right,middle,x;
     int a[N]={2,5,6,8,9,12,24,32,38,40};
    cout << "输入个要查找的数： ";
     cin>>x;
     for (left=0,right=N-1;left<=right;)
    {
        middle=(left+right)/2;
        if (x==a[middle])
            break;
        else if (x<a[middle])
            right=middle-1;
        else
            left=middle+1;
    }
     if (x==a[middle])
        cout<<"a["<<middle<<"]="<<x<<endl;
     else
        cout<<"查找不到"<<x<<endl;

    本回答被提问者和网友采纳
    第2个回答  2008-11-27
    if (x=a[i]) /* 应该是x==a[i]吧 */

    用递归实现，程序会很好理解
    int f(int a[],int x, int start,int end)
    {
    int i=start+(end-start)/2;
    if(start>end) return -1;/* 没找到，返回-1 */
    if(a[i]==x) return i;
    else if(a[i]>x) return f(a,x,i+1,end);
    else return f(a,x,start,i-1);
    }
    --------------------------------------------------------------------------
    修改如下：
    #include<stdio.h>
    void main()
    {
    int a[15],x,i,start,end;
    printf("input 15 numbers:\n");
    for(i=0;i<15;i++) scanf("%d",&a[i]);
    printf("please enter the number:\n");
    scanf("%d",&x);
    for(start=0,end=14;start<=end;)
    {
    i=start+(end-start)/2;
    if (x==a[i])
    {
    printf("%d",i+1);
    getch();
    return;
    }
    else if (x>a[i]) end = i-1;
    else start=i+1;
    }
    }
    第3个回答  2013-05-08

    亲，你对折半查找的理解完全错误了。

    min 和 max 不是指 容器中的最大元素 和最小元素，指的是元素在容器中的位置。


    折半查找，仅仅要求容器内元素是 有序的就ok了。


    我替你码的代码

    #include <iostream>
    void main() {
        int a[]={20,19,16,15,14,13,12,10,9,7,6,5,3,2,1};
        const int size = sizeof(a) / sizeof(int);
        int x;
        std::cout << "please input a number: ";
        std::cin >> x;
        int low = 0, high = size - 1;
        int mid;
        bool found = false;
        while (low <= high) {
            mid = (low + high) / 2;
            if (a[mid] > x) {
                high = mid - 1;
            } else if (a[mid] < x) {
                low = mid + 1;
            } else {
                found = true;
                break;
            }
        }
        if (found) {
            std::cout << "at " << mid << std::endl;
        } else {
            std::cout << "not found!" << std::endl;
        }
    }

    第4个回答  2008-11-27
    首先，应当声明两个变量来记录这般查找空间的范围，这里我们定义begin和end；其次判断语句if(x=a[i])中x=a[i]是赋值语句，"=="是判断相等运算符，应该为if(x == a[i]);最后，主函数为int型，应最后返回0表示运行成功，即在程序结尾家return 0;

    以下是我在你代码基础上略加修改，已通过运行并成功。
    #include<stdio.h>
    int main()
    {
    int a[15],x,y,i;
    printf("input 15 numbers:\n");
    for(i=0;i<15;i++)
    scanf("%d",&a[i]);
    printf("please enter the number:\n");
    scanf("%d",&x);
    int begin = 0, end = 14;
    while(begin <= end)
    {
    i = (begin + end) / 2;
    if (x==a[i])
    {
    y=i+1;
    printf("%d",y);
    break;
    }
    else
    if (x>a[i])
    end = i - 1;
    else
    begin = i + 1;
    }
    return 0;
    }
    12
    相似回答
    大家正在搜
    相关问题
    C++折半查找的基本思想和步骤
    用C++语言编写折半查找算法的程序
    求问一个C++问题 关于折半查找法
    C++顺序查找法和折半查找法谁能各举一个简单的例子呀！谢啦！
    用C++语言改写折半查找算法，使其采用递归的调用
    给我个C++实现二分查找的算法
    c++如何用二分查找算法（Binary Search）找出文...
    c++如何用二分查找算法（Binary Search）找出文...