C++编写一个二分查找函数

以下是C++编写的二分查找函数示例：

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2; // 计算中间位置
        if (arr[mid] == target) { // 如果找到目标值，直接返回下标
            return mid;
        } else if (arr[mid] < target) { // 如果中间值小于目标值，缩小搜索范围到右半部分
            left = mid + 1;
        } else { // 如果中间值大于目标值，缩小搜索范围到左半部分
            right = mid - 1;
        }
    }
    return -1; // 如果未找到目标值，返回-1
}

该函数的参数说明：

- `arr[]`：表示需要进行查找的有序数组。
- `left`：表示需要查找的数组的起始下标。
- `right`：表示需要查找的数组的结束下标。
- `target`：表示需要查找的目标值。

函数使用while循环实现二分查找，每次计算中间位置，然后根据中间位置与目标值比较，缩小搜索范围。如果找到目标值，直接返回该元素的下标，否则最后返回-1表示未找到。

相关问题

用C++编写一个实现二分查找的算法

以下是 C++ 实现二分查找的代码示例：

int binary_search(vector<int> arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

该函数接受一个有序数组 `arr` 和目标元素 `target`，返回目标元素在数组中的下标，如果不存在则返回 -1。

算法的核心部分是循环内的判断，如果当前中间元素等于目标元素，则直接返回下标；如果中间元素小于目标元素，则在右半部分继续查找；否则在左半部分查找。由于每次查找都将目标区间缩小一半，因此时间复杂度为 O(log n)。

注意：该函数的参数 `vector<int> arr` 表示使用了 C++ 中的标准库 `vector` 来存储数组。如果使用原始数组，则需要传递数组的指针和长度作为参数。

使用c++编写一个二分查找函数并且1.画控制流图； 分别确定3条路径，满足100％语句覆盖、完全分支覆盖、 完全谓词覆 盖；并推导出相应路的路径谓词表达式； 求解每个谓词表达式，找出至少一条不可行路径； 引入至少一个缺陷，使得某个特定的满足完全分支覆盖准则的测试用例， 。 试提出一种方法，能检测出前一步引入的缺陷。

二分查找的代码：

#include <iostream>
using namespace std;

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (arr[mid] == x)
            return mid;

        if (arr[mid] < x)
            l = mid + 1;

        else
            r = mid - 1;
    }

    return -1;
}

int main()
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result;
    return 0;
}

控制流图：


根据控制流图，可以得到三条路径：

- Path 1: 1-2-3-4-5-6-7-8-9-10
- Path 2: 1-2-3-4-5-6-7-11-12-10
- Path 3: 1-2-3-4-5-6-13

对应的路径谓词表达式：

- Path 1: T
- Path 2: arr[mid] < x
- Path 3: arr[mid] > x

我们可以通过修改输入数组，让某个测试用例不可行。例如，将数组改为 `{2, 3, 4, 10, 10, 40}`，此时输入 `x = 10` 时，函数会返回 3，而不是 4。

为了检测出这个缺陷，我们可以引入额外的检查，例如在 while 循环中增加以下代码：

if (l > r)
    return -1;

这样，当 l > r 时，函数会直接返回 -1，避免出现错误的结果。我们可以通过修改输入数组，让某个测试用例触发这个检查。例如，将数组改为 `{2, 3, 4, 10, 10, 40}`，此时输入 `x = 50` 时，函数会进入死循环，因为 l 和 r 的值不断交替，无法跳出循环。我们可以在这种情况下，加入一个计数器来记录循环次数，如果超过一定次数就认为进入了死循环，从而判断出这个缺陷。