비교 횟수로 이진 검색 최적화

Question

최근 인터뷰에서이 질문을 받았습니다. 이진 검색에서 중간 값보다 큰 값과 다른 값의 두 가지 비교가 있습니다. 한 번만 확인해야하는 방식으로 최적화 할 수 있습니까?

Answer 1

네, 여러 가지 방법으로 가능합니다.

일부 버전의 Fortran ("arithmetic IF"참조)에있는 3 방향 비교를 수행합니다.

x86 (및 기타) 어셈블리에서 트릭을 사용하면 cmp을 사용할 수 있지만 여전히 두 개의 분기를 사용할 수 있습니다.

트릭을 사용하여 Deferred Detection of Equality.

Answer 2

아니요, 불가능합니다. 연산자를 전환 할 수는 있지만 (예 : 더 크고 작음보다 크고 같음) 대신 두 가지 비교가 필요합니다. 바이너리 검색에서 실제로 세 가지 결과가 나옵니다. 두 가지를 비교하고 둘 중 어느 것도 사실이 아니라면 세 번째 결과 만 가능합니다. 예를 들어

: 당신은 주위의 연산자를 전환하면 연루 하나가 변경됩니다

if (lookup < mid) 
    searchLower(); 
else if (lookup > mid) 
    searchUpper(); 
else 
    found(lookup); 

,하지만 당신은 두 comparisions을 항상 필요합니다.