设有n个元素的集合a[0]~a[n-1]是有序的，设计算法从这n个元素中找出值为x 的特定元素。利用分治策略试设计一个算法在n个元素的集合查找待查找元素。使用Dev c++分别用递归和非递归实现编写程序

在有序数组中查找特定元素可以使用二分查找法，这是一种经典的分治策略。这个算法的基本思想是每次将数组分成两半，判断目标值x位于左半部分还是右半部分，直到找到目标值或者确定其不存在。

**递归实现（Binary Search - Recursive）**:

#include <iostream>
using namespace std;

// 递归函数，寻找目标值 x 在数组 a 中的位置
int binarySearch(int arr[], int left, int right, int target) {
    if (left > right)
        return -1; // 如果范围为空，返回-1表示未找到

    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) // 找到目标值
        return mid;
    else if (arr[mid] < target) // 目标值大于中间值，搜索右半部分
        return binarySearch(arr, mid+1, right, target);
    else // 目标值小于中间值，搜索左半部分
        return binarySearch(arr, left, mid-1, target);
}

int main() {
    int a[] = {1, 3, 5, 7, 9, 11}; // 假设这是已排序数组
    int n = sizeof(a)/sizeof(a[0]);
    int x = 7; // 要查找的目标值
    int result = binarySearch(a, 0, n-1, x);
    if (result != -1)
        cout << "Element found at index: " << result << endl;
    else
        cout << "Element not found in the array." << endl;
    return 0;
}

**非递归实现（Binary Search - Iterative）**:

#include <iostream>
using namespace std;

// 非递归版本的二分查找
int binarySearchIterative(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int main() {
    // 同样的数组和变量
    int result = binarySearchIterative(a, 0, n-1, x);
    // 输出结果...
}