lower_bound Trace

첫 번째 이상 위치로 수렴하기

arr[mid] < target 이면 mid까지는 답이 아니므로 버리고, 아니면 mid를 후보로 남겨 둡니다.

인덱스 1이 첫 번째 후보입니다. 같은 값이 여러 개여도 가장 왼쪽 경계를 찾습니다.

mid = 3

arr[3] = 2 이므로 조건은 거짓입니다.

mid도 답 후보라서 hi = mid 로 왼쪽을 유지합니다.

arr[1] = 2 이므로 조건은 다시 거짓입니다.

인덱스 1도 후보라서 hi = mid 로 줄입니다.

arr[0] = 1 이므로 조건은 참입니다.

인덱스 0은 답이 아니어서 lo = mid + 1 입니다.

참arr[mid] < target 이면 왼쪽은 답이 아닙니다.

거짓mid가 첫 후보일 수 있으므로 버리지 않습니다.

종료lo == hi 가 되면 그 위치가 경계입니다.

lower_bound = 1 첫 번째 >= 2 위치이며, 중복 값의 시작점입니다.