Почему бинарный поиск не работает в моем тесте?

Question

Я только что написал двоичный поиск на c ++, используя массивы, но он не работает для всех моих тестов.

#include <iostream>
using namespace std;

int bSearch(int arr[], int item);

int main() {
    int testArr[] = {1, 3, 5, 7, 9, 10, 12, 13, 15, 16, 18, 20};
    int result = bSearch(testArr, 18);
    cout << "The result of binary search is " << result << endl;
    return 0;
}

int bSearch(int arr[], int item) {
    int start = 0;
    int middle(0), guess(0);
    int finish = sizeof(arr);

    while(start <= finish) {
        middle = (start + finish) / 2;
        guess = arr[middle];

        if(guess == item)
            return middle;
        else if(guess > item)
            finish = middle - 1;
        else
            start = middle + 1;
    }

    return -1;
}

Можете ли вы объяснить мне, почему это так?

Answer 1

В bSearch параметр arr является не массивом, а указателем на int. Нет никакой информации о том, указывает ли он на массив целых или количество элементов может быть частью такого массива. Поэтому sizeof(arr) будет размером указателя (обычно 4 или 8).

Вам нужно будет передать число элементов, содержащихся в массиве, в bSearch или использовать один из стандартных контейнеров, которые отслеживают размер (std::vector или std::array).