杨乙燃5132 2022-05-08 23:21 采纳率: 100%
浏览 35
已结题

二分查找的递归算法和非递归算法

接收用户输入的10个数,完成如下操作:
(1)接收用户输入的1个数,运用二分查找法查找该数是否在数据序列中;
(2)要求编写二分查找的递归算法和非递归算法,并分别进行测试。

  • 写回答

1条回答 默认 最新

  • 叶落秋白 后端领域优质创作者 2022-05-09 11:40
    关注
    #include<iostream>
    using namespace std;
    //自己完成二分查找的递归和非递归算法
    //非递归二分查找算法
    int twoFind1(int A[], int len, int K)
    {
        int low = 0, high = len - 1,middle;
        if (low > high) return -2;
        while (low <= high)//包含等于的情况
        {
            middle = (low + high) / 2;
            if (K == A[middle]) return middle;
            else if (K > A[middle]) low = middle + 1;
            else high = middle - 1;
        }
        return -1;
    }
    int twoFind2(int A[], int len, int K)
    {
        int low = 0, high = len - 1,middle;
        if (low > high) return -2;
        while (low < high)//不含等于的情况,并在最后做判断
        {
            middle = (low + high) / 2;
            if (K == A[middle]) return middle;
            else if (K > A[middle]) low = middle + 1;
            else high = middle - 1;
        }
        if (low == high && A[low] == K) return low;
        return -1;
    }
    //递归二分查找算法
    int twoFind3(int A[], int k, int low, int high)
    {
        int middle=0;
        if (low > high) return -1;
        middle = (low + high) / 2;
        if (low==high && A[middle] == k) return middle;
        if (low < high) {
            if (A[middle] < k)      return  twoFind3(A, k, middle + 1, high);
            else  if(A[middle]==k)  return middle;
            else                    return  twoFind3(A, k, 0, middle - 1);
        }
        return -1;
    }
    void Init_A(int *A,int n)
    {
        int value = 0;
        cout << "请用户输入10个数据:" << endl;
        for (int i = 0; i < n; i++)
        {
            cin >> value;
            A[i] = value;
        }
    }
    int main()
    {
        int k = 0,m=0,l=0;
        int * A = new int[10];
        Init_A(A,10);
        int len = 10;
        cout << "非递归测试1:" << endl;
        cout << "要查找的元素值为:"; cin >> k;
        cout << "所查找元素在数组中的位置为第:" << twoFind1(A, len,k) + 1 << "个" << endl;
        cout << "非递归测试2:" << endl;
        cout << "要查找的元素值为:"; cin >> l;
        cout << "所查找元素在数组中的位置为第:" << twoFind2(A, len,l) + 1 << "个" << endl;
        cout << "递归算法测试:" << endl;
        cout << "要查找的元素值为:"; cin >> m;
        cout << "所查找元素在数组中的位置为第:" << twoFind3(A, m, 0, len - 1) + 1 << "个" << endl;
    }
    

    img


    源码依法,可自行测试数据

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 5月17日
  • 已采纳回答 5月9日
  • 创建了问题 5月8日

悬赏问题

  • ¥15 怎么看 cst中一个面的功率分布图,请说明详细步骤。类似下图
  • ¥15 为什么我的pycharm无法用pyqt6的QtWebEngine
  • ¥15 FOR循环语句显示查询超过300S错误怎么办
  • ¥15 数电设计题 没有设计思路 不知道用什么芯片进行设计 求提供设计思路
  • ¥60 设计一种优化算法结合案例给出智能仓储四向穿梭车的调度计划
  • ¥15 Errno2:No such file or directory,在当前文件确实没有该图片,怎么解决?
  • ¥15 博世摄像头数据存储的问题(iscsi)
  • ¥15 如何实现对学生籍贯信息管理系统的选择排序
  • ¥15 git clone报错
  • ¥15 3d-slicer超声造影动态图像导入报错