C语言经典算法（九）——递归实现二分查找的两种方法

水深无声 2022-06-02 09:15 229阅读 0赞

后继续整理算法并写出自己的理解和备注。 C++实现的：递归实现二分查找算法

1、 递归实现二分查找  
<1> 题目描述:针对数据，进行二分查找(要求:数据的排列有序)  
<2> 方法一:概念法  
<3> 方法二:递归法  
源码:  
一、 递归实现二分查找  
1、 概念法

#include<iostream>
    #include<assert.h>
    using namespace std;
    int Search(int ar[], int n, int key)
    {
        int low = 0;//低位值
        int high = n-1;//高位值是元素个数-1
        int mid;
        while(low <= high)
        {
            mid = (low+high)/2;
            if(key < ar[mid])
            {
                high = mid-1;//二分
            }
            else if(key > ar[mid])
            {
                low = mid+1;//二分
            }
            else
                return mid;//找到值
        }
        return -1;//查找数据不存在
    }
    void main()
    {
        int ar[10] = {
       12,23,34,45,56,67,78,89,90,100};//这种算法只能在数组有序的情况使用，如果无序，先进行排序
        int n = sizeof(ar)/sizeof(int);
        int key;
        cout<<"请输入要查找的key值:>";
        cin>>key;
        cout<<"pos :> "<<Search(ar,n,key)<<endl;
    }

2、 递归法

#include<iostream>
    #include<assert.h>
    using namespace std;
    int Search(int ar[], int low, int high, int key)
    {
        if(low > high)//查找不到
            return -1;
        int mid = (low+high)/2;
        if(key == ar[mid])//查找到
            return mid;
        else if(key < ar[mid])
            return Search(ar,low,mid-1,key);
        else
            return Search(ar,mid+1,high,key);
    }
    void main()
    {
        int ar[10] = {
       12,23,34,45,56,67,78,89,90,100};
        int n = sizeof(ar)/sizeof(int);
        int key;
        cout<<"请输入要查找的key值:>";
        cin>>key;
        cout<<"pos :> "<<Search(ar,0,n-1,key)<<endl;
    }