如何使用C++中的二分搜索算法-C++-PHP中文网

如何使用C++中的二分搜索算法

WBOY

发布： 2023-09-22 08:24:25

原创

1612人浏览过

如何使用c++中的二分搜索算法

如何使用C++中的二分搜索算法

二分搜索算法（Binary Search）是一种高效的搜索算法，它通过将有序的数据集合分成两半，每次都在数据集合的中间位置进行搜索，通过比较中间位置的值与目标值的大小关系，不断缩小搜索范围，直到找到目标值或者确定目标值不存在为止。下面将介绍如何在C++中使用二分搜索算法，并给出具体的代码示例。

确定搜索范围
在使用二分搜索算法之前，首先需要明确要搜索的数据集合是有序的。例如，我们有一个有序的整数数组nums，要在其中搜索某个目标值target。
定义二分搜索函数
在C++中，我们可以定义一个函数来实现二分搜索算法。该函数的输入参数包括要搜索的数组、数组的起始位置和结束位置，以及目标值target。函数的返回值为目标值在数组中的索引，如果目标值不存在，可以返回一个特定的值（例如-1）。

具体的函数定义如下：

int binarySearch(int nums[], int start, int end, int target) {
    // 定义二分搜索的起始位置和结束位置
    int left = start;
    int right = end;
    
    while (left <= right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;
        
        // 如果中间位置的值等于目标值，直接返回索引
        if (nums[mid] == target) {
            return mid;
        }
        
        // 如果中间位置的值大于目标值，更新结束位置
        else if (nums[mid] > target) {
            right = mid - 1;
        }
        
        // 如果中间位置的值小于目标值，更新起始位置
        else {
            left = mid + 1;
        }
    }
    
    // 目标值不存在，返回-1
    return -1;
}

登录后复制

调用二分搜索函数
通过调用二分搜索函数，我们可以得到目标值在数组中的索引。例如，我们有一个有序数组nums，要搜索目标值target。可以使用以下代码来调用二分搜索函数：

int nums[] = {1, 3, 5, 7, 9};
int n = sizeof(nums) / sizeof(nums[0]);
int target = 5;
int index = binarySearch(nums, 0, n - 1, target);

if (index != -1) {
    cout << "目标值的索引为：" << index << endl;
}
else {
    cout << "目标值不存在！" << endl;
}

登录后复制

在以上代码中，我们首先定义了一个有序数组nums，然后计算数组的长度n。接着定义了目标值target，并调用二分搜索函数binarySearch来搜索目标值的索引。最后根据函数返回的结果进行输出。