C++通過遞歸二進制搜索

我收到的時候第一recursice呼叫犯了一個錯誤，該錯誤：C++通過遞歸二進制搜索

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'不會返回'pEnd'指向的int值。爲了獲得指針的值，你可以使用（如你在固定函數中正確完成的）* * pEnd。 – NoseKnowsAll

@ R-Sahu我錯過了給予反饋，對不起。這非常有幫助，謝謝！ – MattiasLarsson

@MattiasLarsson，不用擔心。都很好。 –

你想if ((pEnd - pBegin) == 0)？請注意，沒有取消引用指針。因爲它不指向任何東西，所以解除引用永遠是一個壞主意。

來源

2015-10-20 18:54:55

C++通過遞歸二進制搜索

回答

相關問題