limd123   2년 전

이 문제 뿐만 아니라 이분 탐색의 개념에 대한 질문이 있습니다. 

이분 탐색 알고리즘을 짤 때 start 와 end 값에 어떨 때는 mid를 넣고 어떨 때는 mid+1, mid-1을 넣어서 범위를 조정해 주던데, 정확히 구분하는 기준이 뭔지 모르겠습니다. 다른 이분 탐색문제에서는 mid를 넣어도 맞는 경우가 있는데 이 문제의 경우 mid를 넣으면 무한루프가 발생합니다. 제가 잘못 알고 있는 부분을 고쳐주시면 감사하겠습니다.

snrnsidy   2년 전

이분 탐색의 종료 조건에 따라서 달라집니다. 즉, lo와 hi를 포함한 구간에 대해서 이분 탐색을 할 때는 글쓴이님이 작성하신 것처럼 while(lo<=hi)로 하는데요. 이 때, update할 때, mid로 갱신을 한다면 나중 가서는 lo = hi = mid가 되어서 종료가 되지 않겠죠? 

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