✏️ 이진 탐색 이란?
📍 기본 이론
- 이진 탐색은 data 가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘 이다.
- 대상 data 의 중앙값과 찾고자 하는 값을 비교해 data 의 크기를 절반씩 줄이면서 대상을 찾는다.
- O(logN) 의 시간 복잡도를 갖고 있다.
📍 핵심 이론
- 오름차순으로 정렬된 data 일 경우 아래의 과정을 반복하면 된다.
- 현재 data 의 중앙값을 선택한다.
- 중앙값 > 타깃 data 일 때 중앙값 기준으로 왼쪽 data 를 선택힌다.
- 중앙값 < 타깃 data 일 땐 오른쪽을 선택한다.
- 중앙값 == 타깃 data 가 될 때 까지 반복한다.
✏️ 사용 방법
1. 오름차순 정렬
- 탐색할 배열을 오름차순 정렬해줘야 한다.
- 라이브러리를 사용해 정렬을 할 경우 Collections.sort 가 가장 빠르다.
Arrays.sort = 병합 정렬 방식 ( 평균 - NlogN / 최악 - N^2 )
Collections.sort = 트리 정렬 방식 ( 최선 - 2N / 평균 NlogN )
2. 배열 중간 index 찾기
int start = 0, end = N -1;
int mid = (start + end) / 2;
3. 타깃과 비교하기
static void binary(int start, int end) {
if (target < list.get(start) && target > list.get(end))
return;
while(true) {
int mid = (start + end) / 2;
if (target == list.get(mid)) break;
else if (start == end) break;
else if (target < list.get(mid)) end = mid;
else if (target > list.get(mid)) start = mid + 1;
}
}