c++ - 该值应该在 while 循环结束时还是开始时更新？

Question

我正在练习二分搜索算法，当在迭代直到 start <= end 的 while 循环的开始或结束时更新 mid 的值时，该算法给出了相同的结果。和mid = (start + end)/2知道该值不会溢出。

包含的头文件是:

#include <iostream>
#include <vector>
using namespace std;

主要功能是:

int main(){
    vector<int> arr = {1,3,5,6,6,7,8,9,15};
    int size = arr.size();
    int element = 5;

    // binarySearch(vector<int> arr, int size, key)
    int index = binarySearch(arr, size, element);
    cout << element << " found at index " << index << endl;
    return 0;
}

函数代码:

key是要在 vector 数组 arr 中搜索的元素和size是数组中元素的数量。

    int start = 0, end = size - 1;
    int mid = (start + end)/2;
    while(start <= end){
        // updating the value of mid
        mid = (start + end)/2;
        if(arr[mid] == key){
            return mid;
        }
        else if(key < arr[mid]){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
    }
    return -1;
}

当mid时的代码在 while 循环结束时更新为:

int binarySearch(vector<int> arr, int size, int key){
    int start = 0, end = size - 1;
    int mid = (start + end)/2;
    while(start <= end){
        if(arr[mid] == key){
            return mid;
        }
        else if(key < arr[mid]){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
        // updating the value of mid
        mid = (start + end)/2;
    }
    return -1;
}

是否更新mid在结尾或开头实际上有什么区别吗？？

Answer 1

只要在循环内使用之前进行计算，在哪里执行并不重要。

• 将其放在循环中最后因此需要在循环之前进行预先计算，以便在两个位置具有相同的公式。如果您可以避免这种情况，通常会更好，因为您不想在多个位置修改计算，以防以后需要更改它。

• 出于上述原因，将其首先放置在循环中，就像在第一个代码段中所做的那样。然后，您可以跳过循环之前进行的预计算，最终只得到一个。

在下面的示例中，我没有发送 vector 的大小到函数，因为 vector有一个size()可以使用的功能。该函数返回 std::size_t 类型的值因此我将使用该类型来避免编译器收到有关将有符号变量与无符号变量进行比较的警告(std::size_t 不能保存负值)。这也意味着我不能只做 size() - 1由于采用空 vector 的大小并减去 1会“环绕”并成为一个非常巨大的值(value)。因此我设置end = size()并使用while (start < end)在循环中代替(以及在循环中分配 end = mid 而不是 end = mid - 1)。

我还稍微改变了比较的顺序。如果arr包含许多值，我假设只需要很少的次数来测试相等性，所以我改为测试 if key < arr[mid]或arr[mid] < key 。如果这些都不是 true ，它们必须相等。

示例:

constexpr std::size_t not_found = static_cast<std::size_t>(-1);

size_t binarySearch(const std::vector<int>& arr, int key) {
    std::size_t start = 0, end = arr.size();

    while (start < end) {
        std::size_t mid = (start + end) / 2;

        if (key < arr[mid]) {
            end = mid;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            return mid;
        }
    }
    return not_found;
}

我还添加了一个常量，not_found ，它可以用来确定我们搜索的值是否被发现。用法示例:

std::size_t index = binarySearch(arr, element);

if(index == not_found) {
    std::cout << element << " was not found\n";
} else {
    std::cout << element << " found at index " << index << '\n';
}