CodongCodong   2년 전

이 코드를 제출하면 시간 초과가 되는데 52번째 줄에서 조건을 left>=right로 바꾸면 정답이 됩니다.

left가 탐색하는 범위의 시작값이고 right가 끝값입니다.

아무리 생각해봐도 left가 right보다 크게 될 수는 없을 것 같은데다가 왜 ==으로 하면 시간초과가 되는 지 모르겠어요...

==으로하면 반복문이 안 끝나서 시간초과가 되나요? 그러면 런타임 에러가 될 것 같은데...

고수님들 도와주세요

degurii   2년 전

n = 2, 주어진 배열은 {3, 4}, 찾아야 하는 정수는 1이라고 해보자구요

이분탐색의 범위는 [0, 1]입니다.

left = 0, right = 1, mid = 0인데, A[mid] > target 이므로 

right = -1이 됩니다.

CodongCodong   2년 전

아 그런 예시가 있네요! 감사합니다.

그런데 제가 코드에 배열의 최대값보다 크거나 최소값보다 크면 바로 없다는 결과를 나오게 해 놓았는데 시간초과가 나오는 이유는 무엇인가요?

djm03178   2년 전

꼭 인덱스가 최대나 최소를 벗어나지 않아도 right가 left보다 작아지는 일은 발생할 수 있습니다.

그래서 이분탐색은 기본적으로 루프 조건문을 left <= right로 둡니다.

degurii   2년 전

비슷하게 찾을 수 있습니다.

배열의 개수가 4이고, 찾아야 하는 수 target이 A[1] < target < A[2]라고 해봅시다.

첫번째 반복에서

l = 0, r=3, mid = 1이고 A[mid] < target 이므로 l = 2가 됩니다.

두번째 반복에서

l=2, r=3, mid =2이고, A[mid] > target이므로 r = 1이 되어 l>r이 됩니다

댓글을 작성하려면 로그인해야 합니다.