제가 아직 많이 부족해서 질문을 드립니다.
이분 탐색을 할 때 lo, hi , mid 이렇게 있다면
if(조건) lo = mid;
else hi = mid;
와
if(조건) lo = mid+1;
else hi = mid - 1
이 두 코드의 차이가 크나요?
lo=1
hi=2
mid=(lo+hi)/2=3/2=1
이면
위의 경우 조건을 만족하면 무한루프 돌수 있지 않을까요?
아 그렇네요 그럼 또 하나 질문이 있는데 주로 이분 탐색을 할 때 while문이 보통 while(lo+1<hi)나 while(lo<=hi)로 나뉘던데 각각 어떤 차이가 있는건가요?
저 두개의 코드만 비교해보면 동작은 같습니다.
굳이 차이를 찾자면 전자는 덧셈이 한번더 들어가는 차이 일 것 같습니다.
< 와 <= 는 클럭수가 같은 것으로 알고 있습니다.
컴파일러 최적화 성능에 따라서 차이가 없을 수도 있겠지만요...
그렇군요 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
dsa2341 4년 전
제가 아직 많이 부족해서 질문을 드립니다.
이분 탐색을 할 때 lo, hi , mid 이렇게 있다면
if(조건) lo = mid;
else hi = mid;
와
if(조건) lo = mid+1;
else hi = mid - 1
이 두 코드의 차이가 크나요?