바이너리 검색 코드 디버그

Question

이 인터뷰 질문을 발견했습니다. 정렬 된 배열에서 이진 검색을해야한다는 것입니다. 다음은 그 코드입니다. 이 코드는 정답을주지 않는 버그가 있습니다. 올바른 결과를 내기 위해 코드를 변경해야합니다.

조건 : 줄을 추가 할 수 없으며 코드에서 세 줄만 변경할 수 있습니다.

int solution(int[] A, int X) { 
    int N = A.length; 
    if (N == 0) { 
     return -1; 
    } 
    int l = 0; 
    int r = N; 
    while (l < r) { 
     int m = (l + r)/2; 
     if (A[m] > X) { 
      r = m - 1; 
     } else { 
      l = m+1; 
     } 
    } 
    if (A[r] == X) { 
     return r; 
    } 
    return -1; 
} 

나는 많은 것을 독자적으로 시도했지만 일부 테스트 사례에서는 누락되었습니다.

Answer 1

이 시도 :이 찾았다 경우

int l = 0; 
int r = N - 1; // changed 
while (l <= r) { // changed 

Answer 2

당신은 출구를, 루프 내부의 검색 값을 확인해야 할

샘플 코드 :

int solution(int[] A, int X) { 
    int N = A.length; 
    if (N == 0) { 
     return -1; 
    } 
    int l = 0; 
    int r = N; 
    while (l <= r) { // change here, need to check for the element if l == r 
        // this is the principal problem of your code 
     int m = (l + r)/2; 
     if (A[m] == X) { // new code, for every loop check if the middle element 
      return r; // is the search element for early exit. 
     } else if (A[m] > X) { 
      r = m - 1; 
     } else { 
      l = m + 1; 
     } 
    } 
    return -1; 
} 

다른 문제는 너야 요소가 배열에있을 때 필요한 요소를 더 많이 테스트하고 있습니다.

Answer 3

나는이 질문이 싫지만, 그것은 "불필요한 제약"질문 중 하나입니다. 다른 사람들이 언급했듯이, 문제는 당신이 그것을 찾으면 당신이 가치를 반환하지 않는다는 것입니다.

if (A[m] >= X) { 
    r = m; 
} else { 
    l = m; 
} 

이것은 성능을 죽이고 있지만 작동합니다 : 바보 같은 지침은 코드를 추가 할 수없는 말 때문에, 당신은 이런 식으로 해킹 할 수 있습니다.

Answer 4

사용 된 방법을 이해해야합니다. 넌

당신은 내가 < K < > = A [i]를 < X.

L은 왼쪽위한와 k는 원하는 > = X. 첫번째 요소를 찾고있다. 그것은 k에 대한 하한입니다. 너는 내가있다 < l = > A [i] < X.

R은 오른쪽이다. k의 상한선입니다. 너는 내가있다 > = r = > A [i] > = X.

당신의 목표는 범위를 줄이고 l = r이다. 이렇게하려면 m = (r + l)/2에서 중간 값을 확인하십시오.
A [m] > = X이면 m은 r에 대한 조건을 만족합니다. r = m으로 설정할 수 있습니다.
A [m] < X이면 A [m]은 l의 왼쪽 부분에 속합니다. 그래서 당신은 m, l = m + 1의 오른쪽에 l을 설정할 수 있습니다.

각 루프는 1과 r 사이의 범위를 줄입니다. l == r에 도달하면 k라고 부르는 점을 발견하게됩니다. A [k]는 가장 작은 숫자 인 > = X입니다. == X인지 아니면 >인지 확인해야합니다. X.

거기에서 코드를 수정할 수 있습니다.

추신 : k (별명 l 또는 r)는 > = A. 길이 일 수 있습니다. 그걸 확인해야합니다.