[Java Algorithm] 이분 탐색(Binaray Search)

 🔥 이분 탐색(Binary search)이란?

정렬되어 있는 배열에서 데이터를 찾으려 시도할 때, 순차탐색 처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라 탐색 범위를 절반씩 줄여가며 찾아가는 탐색방법이다.

 

---

🔥 이분 탐색 진행 단계

1. 검사 범위에서 mid값이 존재할 수 있는지 확인한다.

 

2. 해당 값이 찾고자 하는 값이면 반복문을 종료하며 리턴한다.

 

3. 만약 찾고자 하는 값이 작다면 검사범위를 큰 쪽으로 설정해야하기 때문이 left = mid를 한다.

 

4. 만약 찾고자 하는 값보다 크다면 검사 범위를 작은 쪽으로 잡아야 하기 때문에 right = mid를 한다.

 

5. 1 ~ 4번의 단계를 반복문을 통해 반복하다 원하는 값이 나오게 되면 2번 단계에서 반복문이 종료되게 된다.

 

---

 🔥 이분 탐색 예시

T, F 의 값으로만 구성된 TF배열이 있다. 이때 F와 T를 정렬했을 때 F에서 T로 값이 변경되는 지점을 찾는다.

 

char[] TF = { 'F', 'F', 'F', 'F', 'F', 'F', 'T', 'T', 'T', 'T' };

 

시작지점을 배열의 맨 첫 번째 index인 0으로 선택하고 맨 끝 지점을 선언된 배열의 제일 마지막 index를 선택한다.

int start = 0;
int end = TF.length - 1;

 

가운데 지점을 시작지점과 끝지점을 더한 후 2로 나눈 값을 지정하고 해당 값이 F면 아직 T로 바뀐 것이 아니기 때문에 시작지점을 현재 중간지점으로 바꿔준다. 

 

해당 값이 start + 1 이 end 보다 크거나 같게 되면 반복문을 탈출 해야하기 때문에 flag를 false로 바꿔준다.

while (flag) {
	int mid = (start + end) / 2;

	// start 와 end 사이에 칸이 없을 때
	if (start + 1 >= end) {
		flag = false;
    }

	if(TF[mid] == 'F') start = mid;
	else end = mid;
}

 

---

 🔥 시간복잡도

처음부터 끝까지 원하는 값을 찾을 때까지 탐색을 계속하는 순차탐색은 Worst Case일 때 O(n)이라는 시간 복잡도를 보여준다.

10만개이 데이터가 있다면 10만번을 탐색해야 하는 것이다.

 

하지만 이분 탐색은 탐색 대상을 무조건 절반씩 계속해서 줄여나가기 때문에 Worst Case일 때에도 탐색의 횟수가 10만개의 데이터가 있다고하더라도 약 16번 정도로 탐색을 끝 낼 수 있다. 여기서 이분탐색의 시간복잡도는 O(log n)이다.