Бинарный поиск в C с рекурсивной функцией принимает только длину

Question

Я решаю упражнения «Программирование жемчуга». 4.11 Скажите:

Напишите и докажите правильность рекурсивной бинарной функции поиска в C или C ++ с помощью этого объявления:

int binarySearch (dataType x [], int n);

Используйте эту функцию в одиночку; Не вызывайте никакой другой рекурсивной функции.

Я придумал:

int bsearch_rec_array_only(int key, int* arr, int n)
{
    int mid;

    if (n < 0)
        return -1;

    mid = n / 2;

    if (arr[mid] == key)
        return (int) ((size_t) arr + mid * sizeof(*arr));
    else if (arr[mid] < key)
        return bsearch_rec_array_only(key, arr + mid + 1, n - mid - 1);
    else
        return bsearch_rec_array_only(key, arr, mid - 1);
}

Однако - есть проблема. Я возвращаю смещение, включая адрес массива, потому что в противном случае как узнать относительное смещение элемента в исходный массив?

Так что мне нужна эта обертка:

int bsearch_array_only_wrap(int key, int* arr, int n)
{
    int offset;
    if (n == 0)
        return -1;

    offset = bsearch_rec_array_only(key, arr, n);

    if (offset == -1)
        return -1;
    else       
        return (offset - (int) arr) / sizeof(*arr);
}

Это не рекурсивно - это просто вызывает bsearch_rec_array_only и вычисляет смещение.

Но это кажется сложным. Вы можете найти лучшее решение?

Answer 1

Ваша проблема заключается в том, что код не возвращает смещение элемента с начала массива, но указатель бросает в Int. Тот факт, что вы использовали актерский состав, должен показать вам, что в коде что -то не так.

Попробуйте вернуть смещение. Что-то вроде этого:

if (arr[mid] == key)
        return mid;
else if (arr[mid] < key) {
        int i = bsearch_rec_array_only(key, arr + mid + 1, n - mid - 1);
        return (i != -1) ? i + mid + 1 : -1;
} else
        return bsearch_rec_array_only(key, arr, mid - 1);

Answer 2

Вот правильный ответ:

// Recursive binary search
int bsearch(int key, int * arr, int n)
{
    if (n == 0)
    {
        return -1;
    }

    int m = n / 2;
    int found;

    if (arr[m] == key)
    {
        found = m;
    }
    else if (arr[m] < key)
    {
        // Upper half. We'll search in upper half of the current array with new length 
        // of the upper half.
        found = bsearch(key, arr + m + 1, n - m - 1);

        if (found != -1)
        {
            // Since we've found a key, need to offset it to make valid in the 
            // current search scope
            found += m + 1;
        }
    }
    else
    {
        // Lower half, there is no need to offset the array. 
        // New array length is equal to the current middle point.
        found = bsearch(key, arr, m);
    }

    assert(found == -1 || (found >= 0 && found < n && arr[found] == key));

    return found;
}