[已解决]编程实现二分查找算法

王鹿其

c++

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-28 11:32:11

二分查找算法是一种高效的搜索算法，适用于有序数组。它通过将待查找区间逐渐缩小一半来定位目标值。下面是C++中实现二分查找算法的示例代码：

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;  // 目标值不存在
}

int main() {
    std::vector<int> nums = {1, 3, 5, 7, 9};
    int target = 5;
    int result = binarySearch(nums, target);
    
    if (result != -1) {
        std::cout << "目标值 " << target << " 在索引 " << result << " 处找到了。" << std::endl;
    } else {
        std::cout << "目标值 " << target << " 不存在。" << std::endl;
    }
    
    return 0;
}

在上述代码中， binarySearch  函数接受一个有序整数数组  nums  和目标值  target  作为参数。它使用两个指针  left  和  right  来表示待查找区间的左右边界。

在每次循环中，算法计算中间位置  mid ，并将其与目标值进行比较。如果  nums[mid]  等于目标值，则找到了目标值，返回  mid 。

如果  nums[mid]  小于目标值，则目标值可能在  mid  的右侧，因此将  left  更新为  mid + 1 。

如果  nums[mid]  大于目标值，则目标值可能在  mid  的左侧，因此将  right  更新为  mid - 1 。

循环继续直到  left  大于  right ，此时目标值不存在于数组中，返回 -1。

在  main  函数中，我们定义了一个有序数组  nums  和目标值  target ，然后调用  binarySearch  函数进行查找。最后根据返回值判断是否找到目标值，并输出相应的结果。

以上是二分查找算法在C++中的实现。希望对你有帮助！

跳转到最佳答案楼层

isdkz

二分查找算法是一种高效的搜索算法，适用于有序数组。它通过将待查找区间逐渐缩小一半来定位目标值。下面是C++中实现二分查找算法的示例代码：

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;  // 目标值不存在
}

int main() {
    std::vector<int> nums = {1, 3, 5, 7, 9};
    int target = 5;
    int result = binarySearch(nums, target);
    
    if (result != -1) {
        std::cout << "目标值 " << target << " 在索引 " << result << " 处找到了。" << std::endl;
    } else {
        std::cout << "目标值 " << target << " 不存在。" << std::endl;
    }
    
    return 0;
}

在上述代码中， binarySearch  函数接受一个有序整数数组  nums  和目标值  target  作为参数。它使用两个指针  left  和  right  来表示待查找区间的左右边界。

在每次循环中，算法计算中间位置  mid ，并将其与目标值进行比较。如果  nums[mid]  等于目标值，则找到了目标值，返回  mid 。

如果  nums[mid]  小于目标值，则目标值可能在  mid  的右侧，因此将  left  更新为  mid + 1 。

如果  nums[mid]  大于目标值，则目标值可能在  mid  的左侧，因此将  right  更新为  mid - 1 。

循环继续直到  left  大于  right ，此时目标值不存在于数组中，返回 -1。

在  main  函数中，我们定义了一个有序数组  nums  和目标值  target ，然后调用  binarySearch  函数进行查找。最后根据返回值判断是否找到目标值，并输出相应的结果。

以上是二分查找算法在C++中的实现。希望对你有帮助！