设有n个元素的集合a[0]~a[n-1]是有序的，设计算法从这n个元素中找出值 为x的特定元素。 编程任务 利用分治策略试设计一个算法在n个元素的集合查找待查找元素。 数据输入 x和n个元素的数组a[n] 数据输出 与x匹配的数组元素下标或未找到

这里介绍一种基于分治策略的算法，时间复杂度为O(logn)。

1. 将数组a平均分成两个子数组，分别为a~a[mid-1]和a[mid]~a[n-1]，其中mid为数组中间位置。
2. 如果a[mid]等于x，则返回mid。
3. 如果a[mid]大于x，则在左子数组中递归查找。
4. 如果a[mid]小于x，则在右子数组中递归查找。
5. 如果左右子数组都没有找到x，则返回未找到。

下面是算法的Python实现：

def binary_search(a, x, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if a[mid] == x:
        return mid
    elif a[mid] > x:
        return binary_search(a, x, left, mid - 1)
    else:
        return binary_search(a, x, mid + 1, right)

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
result = binary_search(a, x, 0, len(a) - 1)
if result == -1:
    print("未找到")
else:
    print("下标为", result)

相关问题

设有n个元素的集合a[0]~a[n-1]是有序的，设计算法从这n个元素中找出值为x的特定元素 代码

为了在一个已排序的数组`a[0]`到`a[n-1]`中查找指定值`x`，可以使用二分查找算法，它对于有序数组非常有效。以下是Python中的代码实现：

def binary_search(a, n, x):
    low = 0
    high = n - 1

    # 当low <= high时继续查找
    while low <= high:
        mid = (low + high) // 2

        # 如果找到匹配的元素
        if a[mid] == x:
            return mid
        # 如果x小于中间元素，缩小搜索范围到左半部分
        elif a[mid] > x:
            high = mid - 1
        # 否则，缩小搜索范围到右半部分
        else:
            low = mid + 1

    # 如果未找到元素，返回-1表示不存在
    return -1

# 示例
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
index = binary_search(sorted_array, len(sorted_array), target)
if index != -1:
    print(f"元素 {target} 在索引 {index}")
else:
    print(f"{target} 不在数组中")

设有n个元素的集合a[0]~a[n-1]是有序的，设计算法从这n个元素中找出值为x的特定元素 C++代码

要在有序数组`a[0]`到`a[n-1]`中查找值为`x`的元素，可以使用二分查找法。这是一种高效的搜索算法，适用于有序的数据结构。以下是C++实现的代码：

#include <iostream>

// 定义二分查找函数
int binarySearch(int arr[], int left, int right, int x) {
    if (right >= left) {
        int mid = left + (right - left) / 2;

        // 如果中间元素正好是我们要找的值
        if (arr[mid] == x)
            return mid;

        // 如果中间元素大于我们要找的值，则在左半部分继续查找
        else if (arr[mid] > x)
            return binarySearch(arr, left, mid - 1, x);

        // 否则，在右半部分查找
        else
            return binarySearch(arr, mid + 1, right, x);
    }

    // 没有找到，返回 -1 表示元素不在数组中
    return -1;
}

int main() {
    int n;
    std::cout << "Enter the size of the array: ";
    std::cin >> n;

    int a[n];
    std::cout << "Enter the elements of the sorted array: ";
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];

    int x;
    std::cout << "Enter the value to search for: ";
    std::cin >> x;

    int result = binarySearch(a, 0, n - 1, x);
    
    if (result != -1)
        std::cout << "Element found at index " << result << "\n";
    else
        std::cout << "Element not found in the array.\n";

    return 0;
}