이진 검색에서 mid = (beg + end)/2와 mid = beg + (end-beg)/2의 차이점은 무엇입니까?

Question

C++ 입문서 5 판 문제 3.26에서 문제가 있는데, 그 차이점을 모르겠습니다. 두 번째 것이 오버플로를 피할 수 있습니다.

Answer 1

오버플로를 피할 수 있습니다.

정확히. beg+end을 표명 할 수 있다고 보장 할 수는 없습니다. 두 번째 경우 중간 값과 예상 결과는 end보다 크지 않으므로 오버플로의 위험이 없습니다.

두 번째 형식은 포인터 및 기타 임의 액세스 반복기와 같은 아핀 유형에도 사용할 수 있습니다.이 반복자는 거리를 제공하기 위해 빼기는하지만 함께 추가 할 수는 없습니다.

Answer 2

일반적으로 두 표현식이 모두 유효하지 않습니다. 예를 들어 첫 번째 표현식은 포인터 나 반복자에 대해 +와 같은 연산이 없기 때문에 유효하지 않습니다. 두 번째 식은 비 임의 액세스 이터레이터가 사용되는 경우에 유효하지 않습니다. 예를 들어, 양방향 반복자가 사용되는 경우. 우리가 더 일반적인 설정에서 두 줄을 고려하는 경우

그래서 C++에서 올바른 구조는 다음과 같은 방법

mid = std::next(beg, std::distance(beg, end)/2); 

Answer 3

을 보이는 것, 이진 검색 관련이없는 다음과 같은 관측 할 수있다 :

두 번째 폼이 피하려고하는 문제가 오버플로되어 최대로 표현 가능한 숫자보다 큰 숫자를 나타내려고한다는 것입니다.

개별 번호 beg 및 end의 크기에는 제한이 없으므로 둘 다 최대 표현 가능 수의 절반보다 클 수 있습니다. 그것들을 추가하는 것은 중간 결과 (beg + end)가 오버플로 될 수 있음을 의미합니다.

두 번째 솔루션은 오버플로의 위험을 제거하는 것으로 보이지만 또 다른 솔루션을 소개합니다. 값이 부호있는 값인 경우 해당 값의 차이가 다시 초과 될 수 있습니다 (부호에 따라 언더 플로우). 부호없는 값은 아무런 문제가 없습니다.

이 당신이 게시되지 않은 또 다른 솔루션입니다 :

mid = beg/2 + end/2 

이 오버 플로우와 언더 플로우에 모든 문제를 해결하지만, 정밀 손실, 새로운 문제를 소개합니다. 정수 값으로 작동하는 경우, (2)에 의한 분할이 0.5 결과를 수득 함께 이러한 추가 할 미드 1으로 해제 될 수 있음을 의미한다 :

mid = 3/2 + 5/2; // mid is 3, instead of the 4 expected 

부동 소수점 값 작업 다른 정밀도에 문제가있다.

이진 검색을 사용하면 beg 및 end는 부호없는 값이므로 쉽게 확인할 수 있으므로 두 번째 해결 방법은 항상 올바른 결과를 제공합니다.

Answer 4

답은 책에있다 : 반복자가 요소를 나타내지 않는 끝에서 반환하기 때문에

는 "그것은 증가 또는 역 참조 할 수 없습니다."

그래픽으로는 비대칭 범위로 의미가, 는 [