- Today
- 68
- Total
- 244,424
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 2022/08 (1)
- 2022/07 (1)
- 2022/06 (8)
- 2022/05 (5)
- 2022/04 (11)
- 2022/03 (11)
- 2022/02 (1)
- 2022/01 (2)
- 2021/11 (2)
- 2021/10 (2)
- 2021/09 (4)
- 2021/02 (1)
- 2020/07 (1)
- 2020/06 (6)
- 2020/05 (5)
- 2020/04 (5)
- 2020/03 (5)
- 2020/02 (6)
- 2020/01 (6)
- 2019/12 (7)
- 2019/11 (8)
- 2019/09 (7)
- 2019/06 (2)
- 2019/05 (6)
- 2019/04 (4)
- 2019/03 (8)
- 2019/02 (5)
- 2019/01 (2)
- 2018/11 (7)
- 2018/10 (10)
Joonas' Note
Binary search 쉬운 구현 + 설명 본문
2020/03/19 - [개발/C++] - [C++ STL] binary_search, upper_bound, lower_bound 구현하기
[C++ STL] binary_search, upper_bound, lower_bound 구현하기
종종 사용하는 std::binary_search와 그 친구들(lower_bound, upper_bound)의 구현입니다. 이 친구들은 헤더에 있습니다. 평소 쓰던 스타일을 그대로 작성하여 올립니다. binary_search가 왜 그 lower..
joonas.tistory.com
binary_search는 찾는 key와 lower_bound 위의 값이 같은지만 확인하면 된다.
따라서 아래처럼 구현할 수 있다.
bool binary_search(int arr[], int n, const int& key) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (arr[mid] < key)
l = mid + 1;
else
r = mid - 1;
}
return arr[l] == key;
}
굉장히 짧은데, 같은 경우를 처리하는 if문이 없다. 정해진 답은 없지만, 위 코드를 기반으로 설명하고자 한다.
먼저, 3번줄의 while (l <= r) 과 5번줄의 if (arr[mid] < key)만 생각해보자.
while문은 l == r인 순간이 반드시 오고, 그 때 \(mid\)는 \(mid = (l + r) / 2 = (l + l) / 2 = l\) 이다. \(mid\)값이 범위를 벗어나지 않는 것은 자명하다.
그럼 반복문을 돌면서 답은 어디에 있었을까.
반복문의 가장 마지막 순간만 생각해보자.
arr[mid] == key 일 때 else문으로 간다.
r = mid - 1 로 대입하는 데, 정답은 사실 mid이다. 즉, r은 절대 정답이 아니다.
(같은 원소가 여러개 있더라도, 범위를 좁히는 과정에서 이미 a[l]이 확인하였다.)
+ 이후 while(l <= r) 에 의해, r은 l보다 작으므로 종료된다. 위에서 언급한 l == r일 때 mid값을 생각하면 된다.
그러므로 항상 l의 위치에는 정답이 있어야 한다. (정확히는 lower bound이다.)
종료 조건과 if문에서 같은 경우(==)만 잘 처리한다면, 같은 확인 방법으로 취향에 맞게 여러 방식의 구현이 가능하다.
특히, 같은(==) 경우를 어떻게 바꾸냐에 따라 upper_bound로도 바꿀 수 있다.
'알고리즘' 카테고리의 다른 글
[코딩으로 풀어보기] 자동차 번호판의 숫자가 겹칠 확률 (0) | 2021.11.12 |
---|---|
트리의 노드 순서 정리해서 구간으로 만들기 (0) | 2020.05.13 |
Binary search 쉬운 구현 + 설명 (0) | 2020.04.06 |
Palindromic Tree (0) | 2020.04.03 |
Rubik's Race(루빅스 레이스) 풀이 (0) | 2020.03.25 |
[코딩으로 풀어보기] 문제적 남자 : 브레인 유랑단 13회, 신비로운 문제 (2) | 2020.03.05 |
- Tag
- Algorithm, binary search, lower bound, 알고리즘, 이분 탐색, 이진 탐색