이진 탐색에서 중간값 설정하는 방법과 관련해 질문드립니다.

Question

이진탐색에서 중간값을 설정하는 방법과 관련해 질문드립니다. 아래는 제가 막힌 문제 및 제가 작성한 코드입니다.배열의 처음 위치와 마지막 위치를 각각 start, end로 설정하고 반복문을 통해 이진 탐색을 구현하고자 했습니다. 평소에 제가 작성하는 방식대로 처음과 끝을 더한 값의 반틈을 중간값으로 설정한 후 코드를 제출했는데, 시간 초과 에러가 발생하였습니다.중간값을 다른 방식으로 작성하여 문제를 해결하긴 하였으나, 중간값을 구하는 과정에서 두 방식에 어떤 차이가 있는지, 그리고 왜 처음 식처럼 코드를 작성하였을 때 시간이 초과되는지와 관련해 질문을 드리고자 합니다.이진 탐색 문제public int firstBadVersion(int n) { int start &#61; 1; int end &#61; n; while (start <&#61; end){ int mid &#61; start &#43; (end-start)/2; //처음 구현한 방식 //int mid &#61; (start &#43; end)/2; //시간 초과 에러 발생 if (isBadVersion(mid)){ end &#61; mid - 1; } else{ start &#61; mid &#43; 1; } } return start; }

MuDaeng · Answer

아마 버림돼서 어딘가 무한루프 돌았을수도 있어여

드루이드 · Answer

start &#43; end 가 int 범위를 넘어가는 경우가 생길수 있어서 그렇습니다.

이진 탐색에서 중간값 설정하는 방법과 관련해 질문드립니다.

2개의 답변

Q&A 목록