어레이의 중간을 계산할 때 시작 + (종료 - 시작) / 2보다 2를 선호하는 이유는 무엇입니까?

어레이의 중간을 계산할 때 시작 + (종료 - 시작) / 2보다 2를 선호하는 이유는 무엇입니까?

프로그래머들이 공식을 사용하는 걸 본 적이 있어요

mid = start + (end - start) / 2

간단한 공식을 사용하는 대신

mid = (start + end) / 2

배열 또는 목록에서 중간 요소를 찾습니다.

왜 그들은 앞의 것을 사용하나요?

세 가지 이유가 있다.

일단은...start + (end - start) / 2포인터를 사용하고 있어도 동작합니다.end - start넘치지 않아요¹.

int *start = ..., *end = ...;
int *mid = start + (end - start) / 2; // works as expected
int *mid = (start + end) / 2;         // type error, won't compile

두 번째로start + (end - start) / 2해도 넘치지 않는다start그리고.end큰 양의 숫자입니다.서명된 오퍼랜드의 경우 오버플로는 정의되지 않습니다.

int start = 0x7ffffffe, end = 0x7fffffff;
int mid = start + (end - start) / 2; // works as expected
int mid = (start + end) / 2;         // overflow... undefined

(주의:end - start넘칠 수도 있지만start < 0또는end < 0.)

또는 부호 없는 산술에서는 오버플로가 정의되지만 잘못된 답을 제공합니다.단, 부호 없는 오퍼랜드의 경우start + (end - start) / 2와 같은 한 결코 넘치지 않을 것이다end >= start.

unsigned start = 0xfffffffeu, end = 0xffffffffu;
unsigned mid = start + (end - start) / 2; // works as expected
unsigned mid = (start + end) / 2;         // mid = 0x7ffffffe

마지막으로, 당신은 종종 로드를 향해 라운딩을 하고 싶어합니다.start요소.

int start = -3, end = 0;
int mid = start + (end - start) / 2; // -2, closer to start
int mid = (start + end) / 2;         // -1, surprise!

각주

¹ C 규격에 따르면 포인터 감산 결과가 A로 표현되지 않을 경우ptrdiff_t동작은 정의되어 있지 않습니다.다만, 실제로는, 이 경우, IP 주소를 할당이 필요하게 됩니다.char어레이는 전체 주소 공간의 절반 이상을 사용합니다.

우리는 이 사실을 입증하기 위해 간단한 예를 들 수 있다.특정 대규모 배열에서 범위의 중간점을 찾으려고 합니다.[1000, INT_MAX].지금이다,INT_MAX가장 큰 값입니다.int저장할 수 있습니다.라 할지라도1여기에 더해지면 최종값은 음수가 됩니다.

또한.start = 1000그리고.end = INT_MAX.

다음 식을 사용합니다.(start + end)/2,

중점은 다음과 같습니다.

(1000 + INT_MAX)/2=-(INT_MAX+999)/2이 값을 사용하여 인덱스를 작성하려고 하면 분할 오류가 발생할 수 있습니다.

하지만 공식을 이용해서(start + (end-start)/2)다음과 같은 것이 있습니다.

(1000 + (INT_MAX-1000)/2)=(1000 + INT_MAX/2 - 500)=(INT_MAX/2 + 500) 넘치지 않을 거야

다른 사람들이 이미 말한 것을 덧붙이자면, 첫 번째 것은 수학에 관심이 없는 사람들에게 그것의 의미를 더 명확하게 설명한다.

mid = start + (end - start) / 2

다음과 같이 표시됩니다.

mid는 start + 길이의 절반입니다.

반면:

mid = (start + end) / 2

다음과 같이 표시됩니다.

mid는 start + end의 절반입니다.

적어도 그렇게 표현했을 때는 처음처럼 명확하지 않은 것 같다.

Kos가 지적한 바와 같이 다음과 같은 내용이 있습니다.

mid는 시작과 종료의 평균입니다.

적어도 제 의견으로는 첫 번째처럼 명확하지는 않지만요.

start + (end-start) / 2는 가능한 오버플로를 방지할 수 있습니다(예: start = 2^20 및 end = 2^30).

언급URL : https://stackoverflow.com/questions/38688028/why-prefer-start-end-start-2-over-start-end-2-when-calculating-the