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

王鹿其

c++

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-28 11:32:11

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

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. int binarySearch(const std::vector<int>& nums, int target) {
   
5.     int left = 0;
   
6.     int right = nums.size() - 1;
   
7. 
   
8.     while (left <= right) {
   
9.         int mid = left + (right - left) / 2;
   
10.         
    
11.         if (nums[mid] == target) {
    
12.             return mid;
    
13.         } else if (nums[mid] < target) {
    
14.             left = mid + 1;
    
15.         } else {
    
16.             right = mid - 1;
    
17.         }
    
18.     }
    
19. 
    
20.     return -1;  // 目标值不存在
    
21. }
    
22. 
    
23. int main() {
    
24.     std::vector<int> nums = {1, 3, 5, 7, 9};
    
25.     int target = 5;
    
26.     int result = binarySearch(nums, target);
    
27.    
    
28.     if (result != -1) {
    
29.         std::cout << "目标值 " << target << " 在索引 " << result << " 处找到了。" << std::endl;
    
30.     } else {
    
31.         std::cout << "目标值 " << target << " 不存在。" << std::endl;
    
32.     }
    
33.    
    
34.     return 0;
    
35. }
    

复制代码

在上述代码中， 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++中实现二分查找算法的示例代码：

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. int binarySearch(const std::vector<int>& nums, int target) {
   
5.     int left = 0;
   
6.     int right = nums.size() - 1;
   
7. 
   
8.     while (left <= right) {
   
9.         int mid = left + (right - left) / 2;
   
10.         
    
11.         if (nums[mid] == target) {
    
12.             return mid;
    
13.         } else if (nums[mid] < target) {
    
14.             left = mid + 1;
    
15.         } else {
    
16.             right = mid - 1;
    
17.         }
    
18.     }
    
19. 
    
20.     return -1;  // 目标值不存在
    
21. }
    
22. 
    
23. int main() {
    
24.     std::vector<int> nums = {1, 3, 5, 7, 9};
    
25.     int target = 5;
    
26.     int result = binarySearch(nums, target);
    
27.    
    
28.     if (result != -1) {
    
29.         std::cout << "目标值 " << target << " 在索引 " << result << " 处找到了。" << std::endl;
    
30.     } else {
    
31.         std::cout << "目标值 " << target << " 不存在。" << std::endl;
    
32.     }
    
33.    
    
34.     return 0;
    
35. }
    

复制代码

在上述代码中， 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++中的实现。希望对你有帮助！