이진탐색

이진탐색

찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소 관계에 따라 특정 구간으로 이동하는 것을 반복.

전제

숫자들이 좌에서 우측으로 커진다는 전제에서 가능하므로, 숫자들은 항상 정렬되어있어야 한다.

 

가운데의 숫자를 선택하고

해당 숫자보다 크다면 우측(최소 값 위치를 타겟 숫자 + 1로 변경, 최대 값 위치 유지)

작다면 좌측 범위를 선택하게 되는 것(최소 값 위치 유지, 최대 값 위치를 타겟 숫자 -1로 변경)

 

시간복잡도는 구간의 길이가 1이 될때까지 계속해서 반으로 감소하는 것을 반복하기 때문에, 루프는 약 log2​N 번 돌게 된다. 루프 내부 연산의 시간 복잡도는 O(1)이기 때문에, 자연스럽게 시간복잡도는 O(1∗logN)=O(logN)

 

이진 탐색을 사용 하는 이유는 순차탐색보다 빠르기 때문이다.

하지만 정렬을 추가로 진행한다고 가정할 때, 퀵 정렬을 사용 후 이진 탐색을 진행하면 O(NlogN)이 추가적으로 사용되므로 순차탐색에 비해 느려진다.

즉 정렬이 되어있지 않거나, 탐색하고자 하는 총 숫자의 개수가 적다면 순차탐색이 더 좋은 선택이 될 수 있다.

 

정렬이 되지 않은, 규모가 큰 배열에서, 적은 수를 찾아야 하는 경우 -> 반복이 적으므로 순차 탐색이 빠를 수 있다.

정렬이 되지 않은, 규모가 큰 배열에서, 많은 수를 찾아야 하는 경우 -> 정렬 진행 후 이분탐색을 진행하는 것이 빠를 수 있다.

 

정렬이 되어 있다면 규모가 크든 작든, 적은수든 많은 수든 순차탐색은 O(N)이며 이진 탐색은 O(logN)이므로 이진 탐색이 빠르다.

 

코드

public static int binarySearch(int[] arr, int target) {
	int left = 0;
	int right = arr.length - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] == target) {
			return mid;
		}

		if (arr[mid] > target) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return -1;
}