0. 이진 탐색(Binary Search)
이진 탐색은 타겟(원하는 값)을 찾을 때까지 이진 탐색을 반복 수행하며 검색 범위를 반으로 줄여가면서 순차 탐색보다 빠르게 검색을 수행하는 알고리즘이다.
단, 이진 탐색을 하기 위해서는 자료가 정렬된 상태여야 하는 제약이 존재한다.
분할 정복을 기반으로 하는 방식으로, 분할 정복을 알고 있다면 더욱 이해하기 쉽다.
1. 이진 탐색의 로직
- 자료의 중앙에 있는 원소를 고른다.
- 중앙값(중앙 원소의 값)과 타겟을 비교한다.
- 중앙값과 타겟이 일치하면 탐색을 끝낸다.
- 타겟이 중앙값보다 작으면 자료의 왼쪽 반에 대해 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해 새로 검색을 수행한다.
- 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다
아래 그림은 6을 찾는 이진 탐색의 그림이다.
2. 코드
코드는 재귀와 반복문으로 구현이 가능하다.
여기서는 반복문으로 구현을 해보았다.
사실 Arrays나 Collection에서 binarySearch 메서드를 지원하기 때문에 직접 구현하지 않아도 된다.
3. lower bound & upper bound
배열에 중복된 값이 있을 경우에는 lower bound와 upper bound로 나눠서 이진 탐색을 생각할 수 있다.
lower bound는 찾으려는 값과 같거나 큰 값 중 가장 작은 값을 찾는 것이고 → 이상
upper bound는 찾으려는 값보다 큰 값 중 가장 작은 값을 찾는 방식이다. → 초과
3-1. lower bound 코드
3-2. upper bound 코드
반응형