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

Question

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

Answer 1

#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;
}

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