《数据结构、算法与应用》第一章习题1.6(递归查询数组中是否包含某元素)

//
//  main.cpp
//  Test_06
//
//  Created by cc on 14-4-13.
//  Copyright (c) 2014年 cc. All rights reserved.
//

/*
 6. 试编写一个递归函数来确定元素 x 是否属于数组 a[0: n-1]。
 */

#include <iostream>

using namespace std;

template <typename T>
bool isBelongToArray(T x, T* array, int cur, int last);

template <typename T>
bool isBelongToArray(T x, T* array, int lenth);


int main(int argc, const char* argv[]) {

    //test intArray
    
    int intArray[] = {0, 1, 2, 5, 26};
    int lenth = sizeof(intArray) / sizeof(int);
    int x1 = 21;
    
    if (isBelongToArray(x1, intArray, 0, lenth - 1)) {
        cout << "x1属于数组intArray" << endl;
    } else {
        cout << "x1不属于数组intArray" << endl;
    }
    
    //test charArray
    
    char charArray[] = {‘a‘, ‘b‘, ‘c‘, ‘f‘, ‘s‘};
    int lenth2 = sizeof(charArray) / sizeof(char);
    char x2 = ‘s‘;
    if (isBelongToArray(x2, charArray, lenth2)) {
        cout << "x2属于数组charArray" << endl;
    } else {
        cout << "x2属于数组charArray" << endl;
    }
    
    return 0;
}


/**
 *	@brief	元素x是否属于array
 *
 *	@param 	x       元素x
 *	@param 	array 	数组array
 *  @int    cur     当前索引
 *  @int    high    n-1
 *
 *  @return true: 是 false: 否
 */
template <typename T>
bool isBelongToArray(T x, T* array, int cur, int last) {
    if (cur == last && x != array[cur]) {
        //找到第n-1个元素没找到
        return false;
    } else if (cur <= last && x == array[cur]) {
        //找到了
        return true;
    } else {
        return isBelongToArray(x, array, cur + 1, last);
    }
}

/**
 *	@brief	元素x是否属于array
 *
 *	@param 	x       元素x
 *	@param 	array 	数组array
 *	@param 	lenth 	数组长度
 *
 *  @return true: 是 false: 否
 */
template <typename T>
bool isBelongToArray(T x, T* array, int lenth) {
    if (lenth == 0) {
        return false;
    }
    
    if (x == array[lenth - 1]) {
        return true;
    } else {
    
        return isBelongToArray(x, array, lenth - 1);
    }
}