이진 검색 알고리즘이 바닥과 천장이 아닌 이유 - 반 오픈 범위가 아님

Question

예를 들어 0에서 n 사이의 인덱스를 가진 배열이있을 때. 중간 색인을 계산할 때 바닥이나 천장을 사용하여 이진 검색을 사용하면 같은 결과가 나옵니다.

int middle = ceiling ((left + right)/2);

바닥 천장을 사용하는 이유가 있습니까? 천장을 사용하여 어떤 버그가 발생합니까?

Answer 1

복잡성에는 차이가 없습니다. 두 변형 모두 log (n)입니다. 배열이

0 1 1 1 1 2 

처럼 예를 들어 외모와 1의 인덱스를 찾는 경우

는 구현의 나머지 부분에 따라 다른 결과를 얻을 수 있습니다.

Answer 2

천장을 사용하는 경우 하나의 요소 만 남겨두면 무한 루프가 발생할 수 있습니다. 그 범위를 벗어나도 여전히 한 요소 시퀀스가 ​​산출되기 때문입니다. 그래도 중간 요소는 필요하지 않으므로 비교 후에 요소의 나머지 범위를 줄일 수 있습니다. 그러면 루프가 종료됩니다.

Answer 3

이 내용은 모두 left 및 right 변수를 업데이트하는 방법에 따라 다릅니다.

일반적으로 left = middle+1 및 right = middle-1을 사용하며 중지 기준은 left = right입니다.

이 경우 중간 값의 천장이나 바닥은 중요하지 않습니다.

그러나 left = middle+1과 right = middle을 사용하는 경우 중간 값의 바닥을 가져야합니다. 그렇지 않으면 무한 루프가됩니다.

배열 11, 22에서 11을 찾아보십시오.

우리는 left = 0 및 right = 1가, 중간 우리가 천장을 경우, 그것은 1 될 것 0.5입니다 설정합니다. 22이 쿼리보다 크기 때문에 오른쪽 절반을 잘라내어 오른쪽 경계선을 가운데로 이동해야합니다. 배열이 큰 경우에도 두 개의 요소 만 있기 때문에 잘 작동합니다. right = middle은 right에서 1으로 다시 설정됩니다. 무한 루프가 있습니다. left = middle+1 및 right = middle-1

천장이 모두 천장과 바닥 잘 작동이 left = middle 및 right = middle-1

바닥으로 잘 작동

• 요약하면

  는 left = middle+1 및 right = middle