с ++ Двоичный поиск по рекурсии

я получаю сообщение об ошибке, когда первый вызов recursice сделана ошибка:с ++ Двоичный поиск по рекурсии

Unhandled exception at 0x002A2E44 in rekBinSearch.exe: 0xC0000005: Access violation reading location 0x0000000A.

Это вызвано:

if ((*pEnd - pBegin) == 0) / There's only one element */

Кажется, что, когда я установить новый начальный и конечный адрес, я делаю что-то неправильно, потому что они не могут быть прочитаны при рекурсивном вызове. Они «установить» по:

find(x, (int*)pBegin, pMid);

Полный код:

bool find(const int x, const int* pBegin, const int* pEnd) 
{ 
    if ((*pEnd - *pBegin) == 0) /* There's only one element */ 
    { 
     if (x == (int)pEnd) /* That element could be the correct one */ 
      return true; 
     else     /* If it is not then return false, x is not in the array */ 
      return false; 
    } 

    int *pMid = (int*)(pEnd - pBegin); /* pMid should be the adress to the element in the middle of the array */ 
    if (x >= (int)pMid)     /* If x is in array it is to the right of the middle */ 
     find(x, (int*)pMid, pEnd); 
    else        /* If x is in array it is to the left of the middle */   
     find(x, (int*)pBegin, pMid); 

}// find

Что я делаю неправильно или как я думаю неправильно? Спасибо, я заранее.

источник

2015-10-20 MattiasLarsson

Избавьтесь от всех этих бросков, и вы будете на полпути к решению проблемы, я подозреваю. – davmac

'(pEnd - pBegin)' не вычисляет среднюю точку, а число элементов между указателями. Возможно, есть элементы 0x0A? –

Идиоматическое использование итератора, такого как синтаксис, заключается в том, чтобы рассматривать равенство начала и окончания, указывая на пустой интервал. Ваша функция не обнаруживает передачу пустого массива. – jxh

What am i doing wrong or how am i thinking wrong? Thanks i advance.

Задача 1

Вы путанице между указателями и значениями. Примеры:

if ((*pEnd - *pBegin) == 0) /* There's only one element */

if (x == (int)pEnd)

int(pEnd) не получает значение объекта, который pEnd указывает. Он просто обрабатывает значение указателя как int.

Задача 2

Кроме того, вы не возвращаются правильно из рекурсивных вызовов.

find(x, (int*)pMid, pEnd); // Missing return

find(x, (int*)pBegin, pMid); // Missing return

Исправлена функция

Вот версия, которая должна работать.

bool find(const int x, const int* pBegin, const int* pEnd) 
{ 
    if ((pEnd - pBegin) == 0) /* There's only one element */ 
    { 
     return (x == *pEnd); /* That element could be the correct one */ 
          /* If it is not then return false, x is not in the array */ 
    } 

    int midIndex = (pEnd - pBegin)/2; 
    int const* pMid = pBegin + midIndex; /* pMid should be the adress to the element in the middle of the array */ 
    if (x >= *pMid)      /* If x is in array it is to the right of the middle */ 
     return find(x, pMid, pEnd); 
    else        /* If x is in array it is to the left of the middle */   
     return find(x, pBegin, pMid-1); 

}// find

источник

2015-10-20 18:52:54

Я думаю, было бы полезно, чтобы OP повторил, что '(int) pEnd' не возвращает значение' int', на которое указывает 'pEnd'. Чтобы получить значение указателя, вы используете (как вы правильно сделали в своей фиксированной функции) '* pEnd'. – NoseKnowsAll

@ R-Sahu Я пропустил, чтобы дать отзыв, извините. Это очень помогло, спасибо! – MattiasLarsson

@MattiasLarsson, не беспокойтесь. Все хорошо. –

Вы хотите if ((pEnd - pBegin) == 0)? Обратите внимание, что нет указателей разыменования. Отсрочка разыгрывания всегда плохая идея, поскольку она не указывает ни на что.

источник

2015-10-20 18:54:55

с ++ Двоичный поиск по рекурсии

ответ

Смежные вопросы