[알고리즘] Binary Search 알고리즘

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

 

1. 이진 탐색이란?

이진 탐색은 알고리즘 명칭 그대로 탐색을 위한 알고리즘이다. 이진 탐색은 배열 또는 List에서 가운데 값을 기준으로 찾고자 하는 값이 큰지 작은지 판단 후 가운데 값이 찾고자 하는 값보다 작은 경우 왼쪽의 그룹을 반대로 가운데 값이 찾고자 하는 값보다 큰 경우는 오른쪽 그룹을 이용하여 다시 중간 값과 비교하는 방법으로 값을 찾는 방법입니다.

 

※단 이진 탐색은 가운데 값을 기준으로 작으면 왼쪽, 크면 오른쪽을 구분해야 되므로 정렬된 데이터에만 적용이 가능합니다.

 

2. 이진 탐색 방법

정렬된 값 {1, 4, 6, 8, 10, 15, 27, 29, 30, 32, 56, 87}에서 6을 찾는다고 가정했을 때 이진 탐색 방법

 

1. 가장 먼저 가운데 Index인 6번의 위치의 값 27과 6을 비교
   
   
2. 27보다 찾고자 하는 값 6이 작으므로 27 왼쪽의 값들을 이용하여 탐색 진행
   
   
3. {1, 4, 6, 8, 10, 15}에서 가운데 Index인 3번의 위치의 값 8과 6을 비교
   
   
4. 8보다 찾고자 하는 값 6이 작으므로 8 왼쪽의 값들을 이용하여 탐색 진행
   
   
5. {1, 4, 6}에서 가운데 Index인 1번의 위치의 값 4와 6을 비교
6. 4보다 찾고자 하는 값 6이 크므로 4 오른쪽의 값들을 이용하여 탐색 진행
7. {6}은 1개의 수만 남아 있으므로 해당 수와 찾고자 하는 수를 비교하여 같으면 해당 Index를 반환 한다.

 

3. 이진 탐색 시간 복잡도

이진 탐색은 탐색을 진행한 뒤 그다음 탐색을 진행해야 되는 값이 반으로 O(logn)이 됩니다.

 

4. 구현 코드

배열을 직접 절반씩 나누어 진행하는 것을 비효율 적이므로 시작과 끝을 나타내는 변수를 이용하여 절반을 표현하여 코드를 작성하였습니다.

 

int startIndex = 0;
int endIndex = arr.length - 1;

while (startIndex < endIndex) {
	int mid = (startIndex + endIndex) / 2;

	if (arr[mid] > search)
		endIndex = mid - 1;
	else if (arr[mid] < search)
		startIndex = mid + 1;
	else
		return mid;
}

return -1;