欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分法查找(递归实现,非递归实现)

程序员文章站 2024-03-17 23:01:22
...

递归实现:

#include <iostream>

using namespace std;

//递归实现二分查找
int Find(int A[],int a,int b,int key)
{
    if(a>b)
        return 0;
    int mid = (a+b)/2;
    if(A[mid]==key)
        return mid;
    else if(key<A[mid])
        return Find(A,a,mid-1,key);
    else
        return Find(A,mid+1,b,key);
}
int main()
{
    //直接构造一个有序数组
    int A[11];
    for(int i=1;i<11;i++)
    {
        A[i]=i;
    }
    int pivort=Find(A,1,10,8);//查找值为8的数组下标
    if(pivort==0)
        cout<<"Not Find"<<endl;
    else
        cout<<pivort<<endl;
    return 0;
}

非递归实现:

#include <iostream>

using namespace std;

//非递归二分查找
int Find(int A[],int a,int b,int key)
{
    int mid;
    while(a<b)
    {
        mid=(a+b)/2;
        if(key==A[mid])
            return key;
        else if(key<A[mid])
            b=mid-1;
        else
            a=mid+1;
    }
    return 0;
}

int main()
{
    int A[11];
    for(int i=1;i<11;i++)
    {
        A[i]=i;
    }
    int pivort=Find(A,1,10,8);
    if(pivort==0)
        printf("Not Find\n");
    else
        cout<<pivort<<endl;
    return 0;
}

感悟:之前对二分法的理解总停留在递归层面上,通过实现了非递归发现无论是递归还是循环,只要想办法把算法的过程实现就好了,思路都是一样的。

相关标签: 数据结构与算法