바이너리 검색 구현의 문제점은 무엇입니까?

Question

#include <stdio.h> 
int bsearch(int a[], int n, int lo, int hi) { 
    int mid; 
    mid = (hi + lo)/2; 
    if(a[mid] == n) 
     return 1; 
    else if(a[mid] > n) 
     bsearch(a, n, lo, mid); 
    else 
     bsearch(a, n, mid, hi); 
    return 0; 
} 

int main(void) { 
    int n, a[7] = {2, 4, 5, 67, 70, 80, 81}; 
    int hi = 6, lo = 0, j; 
    scanf("%d", &n); 
    j = bsearch(a, n, lo, hi); 
    if(j) 
     printf("Found"); 
    else 
     printf("Not Found"); 
    return 0; 
} 

입력 : 5 출력 : 찾을 수 없음

나는이 결과를 얻고 왜

사람이 말해 줄래?

Answer 1

큰 문제가 해결되도록 수정해야합니다 (코드 주석의 세부 정보 참조).

다음에 이진 검색 기능을 변경

:

int bsearch(int a[], int n, int lo, int hi) 
{ 
    // add base case 
    if (high < low) 
     return 0; // not found 

    int mid; 
    mid=(hi+lo)/2; 
    if(a[mid]==n) 
     return 1; 
    else if(a[mid]>n) 
     return bsearch(a,n,lo,mid-1); // add return 
    else 
     return bsearch(a,n,mid+1,hi); // add return 
} 

이

---

PS : 그리고 main() 몸에 사용량에 따라, 당신은 실제로만을 표시하는 0/1을 반환 할 필요가 값을 포함하거나 아니. 더 명확하게하려면 bool 반환 유형을 사용하도록 제안합니다.

Answer 2

추가 재귀 호출에 "반환", 예컨대 : 그렇지 않으면

return bsearch(a,n,lo,mid); 

, 당신은 bsearch 1을 반환, 그것은 주에 모든 방법을 반환되지 않습니다.

다른 버그가 있으므로 많은 값을 사용하고 IDE 및/또는 printf를 사용하여 현재 발생한 버그를 확인하십시오. 행운을 빌고 재미있게 보내!

Answer 3

bsearch 함수의 return 0; 문은 재귀 호출에 의해 반환 된 값을 단순히 버리기 때문에 항상 실행되기 때문입니다. 재귀 함수에서 먼저 기본 사례를 결정해야합니다. 여기 bsearch에, 기본 케이스는

low <= hi 

이가 추구 값에 대한 검색을 시작하는 참이어야합니다 첫 번째 조건이다이어야합니다. 이 조건이 충족되지 않으면 , 즉 0을 반환해야합니다.

다음으로 함수 호출을 반환하는 값은 표현식입니다. 즉, 값으로 평가됩니다. 단순히 함수를 호출하고 결과로 아무 것도하지 않으면 항상 함수의 마지막 return 문으로 넘어갑니다. 여기에 귀하의 bsearch 함수에있는 문장과 함께 주석의 몇 가지 점을 나열합니다.

int bsearch(int a[], int n, int lo, int hi) { 
    // first check for the base condition here 
    // if(hi < low) return 0; 

    int mid; 

    // can cause integer overflow. should be 
    // mid = lo + (hi - lo)/2; 

    mid = (hi + lo)/2; 
    if(a[mid] == n) 
     return 1; 
    else if(a[mid] > n) 

     // you are doing nothing with the value returned 
     // think of the function call as an expression 
     // return the value of the expression 
     // should be 
     // return besearch(a, n, lo, hi); 

     bsearch(a, n, lo, mid); 
    else 
     // same follows here 
     // should be 
     // return bsearch(a, n, mid, hi); 

     bsearch(a, n, mid, hi); 

    // finally you will always return 0 because this statement is always executed 
    // all cases have been taken care of. 
    // no return statement needed here 
    return 0; 
}