折半查找法c++

折半查找法也称二分查找法，是一种常用的查找算法，适用于有序序列。以下是 C++ 实现代码示例：

int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // 如果中间元素是要查找的元素，则返回它的下标
        if (arr[mid] == x) 
            return mid; 
  
        // 如果中间元素大于要查找的元素，则在左半部分继续查找
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // 否则在右半部分继续查找
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // 如果找不到要查找的元素，则返回 -1
    return -1; 
} 

该函数接收一个有序数组 `arr`，要查找的元素 `x`，以及数组的左端点下标 `l` 和右端点下标 `r`。函数通过递归的方式进行查找，如果找到了要查找的元素，则返回它的下标，否则返回 -1。

相关问题

折半查找法c++从键盘输入一串数字

折半查找法（Binary Search）是一种常见的查找算法，通常用于有序数组中进行快速查找。它通过将数组从中间分开，比较中间值和目标值的大小，来确定目标值在左侧还是右侧，然后递归地在相应的一半中继续查找，直到找到目标值或者确定目标值不存在为止。

以下是使用C++实现的一个简单的折半查找算法示例：

#include <iostream>
using namespace std;

int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) {
            return mid;
        }
        if (arr[mid] > x) {
            return binarySearch(arr, l, mid - 1, x);
        }
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

int main() {
    int n;
    cout << "请输入数组大小: ";
    cin >> n;
    int arr[n];
    cout << "请输入 " << n << " 个数字:\n";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int x;
    cout << "请输入要查找的数字: ";
    cin >> x;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1) {
        cout << "未找到该数字" << endl;
    } else {
        cout << "该数字在数组中的索引为: " << result << endl;
    }
    return 0;
}

C++实现折半查找法

在C++中，折半查找（也称为二分查找）是一种非常高效的在有序数组中查找特定元素的搜索算法。以下是基本的折半查找法的C++实现：

// 定义一个辅助函数用于二分查找
template <typename T>
size_t binarySearch(const std::vector<T>& arr, const T& target) {
    size_t left = 0;
    size_t right = arr.size() - 1;

    // 当左指针小于等于右指针时继续循环
    while (left <= right) {
        // 计算中间索引
        size_t mid = left + (right - left) / 2;

        // 检查中间元素是否为目标值
        if (arr[mid] == target) {
            // 找到目标，返回其索引
            return mid;
        }
        // 如果中间元素大于目标，缩小搜索范围到左半部分
        else if (arr[mid] > target) {
            right = mid - 1;
        }
        // 否则，缩小搜索范围到右半部分
        else {
            left = mid + 1;
        }
    }

    // 没有找到目标，返回一个表示找不到的位置（通常设置为数组长度）
    return arr.size();
}

// 在主程序中使用
int main() {
    // 假设我们有一个已排序的整数数组
    std::vector<int> sortedArray = {1, 3, 5, 7, 9, 11, 13};

    // 输入要查找的目标值
    int searchValue;
    std::cout << "Enter a value to search: ";
    std::cin >> searchValue;

    // 使用二分查找函数查找目标值并输出位置
    size_t position = binarySearch(sortedArray, searchValue);
    if (position != std::vector<int>::npos) {
        std::cout << "Target value found at index: " << position << std::endl;
    } else {
        std::cout << "Target value not found in the array." << std::endl;
    }

    return 0;
}