鱼C论坛

 找回密码
 立即注册
查看: 1173|回复: 1

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

[复制链接]
发表于 2023-10-28 11:31:17 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
c++
最佳答案
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++中的实现。希望对你有帮助!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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++中的实现。希望对你有帮助!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 08:53

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表