
[개발 일기] 2025.01.28 - 이분탐색 (Lower Bound, Upper Bound)
·
개발 일기
개요 코딩테스트를 볼 때 이분탐색을 사용하는 문제는 심심치 않게 나온다. 그리고 이러한 이분 탐색의 세부 알고리즘으로 하한선(Lower Bound)과 상한선(Upper Bound)으로 나뉜다. 오늘은 이 두 알고리즘에 대해 정리해보자. Lower Bound 하한선은 목푯 값 이상인 첫 번째 위치를 찾는 탐색이다. 배열에서 목표 값 이상이 시작되는 가장 작은 인덱스를 반환한다. 쉽게 말하면 목표 값의 시작 위치를 찾는 알고리즘이다. Lower Bound 동작 방식 1. 첫 번째로 left는 찾고자 하는 값이 들어있는 배열의 왼쪽 끝, right는 오른쪽 끝에서 시작한다. 2. left와 right의 중간 인덱스를 나타내는 mid((left + right) / 2)를 계산한다. 만약 arr [..