duddnd904   2년 전

이분 탐색이 끝나는 시점에 end 값이 어떻게, "해당하는 조건을 만족하는 최대 값"을 보장하는지 잘 모르겠습니다

예컨대, 0 ~ 20을 기준으로 이분 탐색을 했을 때, 11 ~ 20 범위일 때 저희가 찾고자 하는 목표 값 7이 나온다고 가정합니다.

그리고 16 ~ 20 범위 일때는 값이 2가 나왔습니다. 이 이상으로 이분 탐색을 해서 범위를 점차 줄여 나가면 16 ~ 17 , 그리고 마지막으로 16 ~ 15로 역전되고,

start와 end가 역전되어 종료됩니다.

저는 해당 end가 목표 값 7을 만족하는 최대 값이 어떻게 보장되는지 잘 모르겠습니다.16 ~ 15 범위에서 목표값 7이 아닌 8이 나올 수 도 있을거 같다고 생각이 되는데 어디서 부터 이해가 잘못된건지 알고싶습니다.

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