이진 탐색(binary search)이란?

정렬된 배열에서 탐색 범위를 지정하여 탐색 범위의 중간값과 탐색하고자 하는 값에 따라서 탐색 범위를 변경하며 특정 값을 찾아가는 방법을 의미합니다.

김두한식(式) 이진탐색법

static int binarySearch(int[] arr, int target) {
	int start = 0, end = arr.length - 1, result = -1;
	Arrays.sort(arr); // {1, 2, 3, 4, 5, 6, 7, 8, 10}
	while (start <= end) {
		int mid = (start + end) / 2; // 탐색 범위의 중간값
		if (arr[mid] == target) return mid + 1;
		else if (arr[mid] > target) end = mid - 1;
		else start = mid + 1;
	}
	return result;
}

public static void main(String[] args) {
	int[] arr = {1, 3, 2, 4, 6, 5, 8, 7, 10};
	int result = binarySearch(arr, 3); // result = 3;
}

우리는 arr이라는 배열에서 3이 몇번째 숫자인지를 찾고 싶어졌습니다. 물론 지금은 가볍게 직접 세볼 수 있지만, 배열의 길이가 길어진다면 힘들어지겠죠? 그럴 때는 과감하게 CPU와 RAM에게 모든 걸 맡기도록 합니다. 우리에게 필요한 건 김두한과 같은 단호한 마음가짐뿐이라는 것을 기억하시면 됩니다.

7.jpg

Step 1. 배열을 정렬해줍니다.

이진 탐색은 정렬된 데이터에 대하여 적용할 수 있기 때문에 과감하게 정렬을 해줍니다. 마음 약해지실 필요 없습니다. Arrays.sort(int[] list)는 O(NlogN)의 효울적인 정렬 알고리즘을 사용하기 때문에 괜찮을 겁니다.

Arrays.sort(arr); // {1, 2, 3, 4, 5, 6, 7, 8, 10}

6.jpg

Step 2. Loop를 돌며 해당 중간 인덱스에 대한 값을 비교해줍니다.

while (start <= end) {
	int mid = (start + end) / 2; // 탐색 범위의 중간값
	if (arr[mid] == target) return mid + 1; //  값을 찾았을 경우 값을 반환해줍니다.
	else if (arr[mid] > target) end = mid - 1; // 해당 값이 작을 경우 마지막 인덱스를 중간 전으롤
	else start = mid + 1; //해당 값이 클 경우 시작 인덱스를 중간 다음으로
}

이진 탐색의 시간 복잡도는?