[알고리즘] 이분 탐색 (binary search)

이분 탐색 (binary search)

정렬된 배열 안에서 특정 원소를 찾을 때,
인덱스 i부터 j의 중간값을 비교해서 중간값이 찾는 원소가 아니라면 인덱스의 i와 j를 재정의 하는 방법으로 탐색한다.
인덱스 i와 j를 정할 때 마다 탐색 범위는 반으로 줄어든다.

 

이분 탐색 방법

1. 처음 범위는 0부터 마지막 인덱스까지다.
   • 이때 중간 인덱스를 mid라고 한다.
2. mid와 찾는 원소를 비교한다.
   1. 찾는 원소와 mid 인덱스의 값이 같다면 탐색을 종료한다.
   2. mid 인덱스의 값 < 찾는 원소일 때는 left = mid + 1로 하여 2를 반복한다.
   3. mid 인덱스의 값 > 찾는 원소일 때는 right = mid - 1로 하여 2를 반복한다.
3. 만약 left > right이 된다면 해당 배열에 찾는 원소가 없는 것이다.

이분 탐색 구현 (java)

1. 반복문

	public static boolean BSearch(int[] arr, int target) { // target: 찾으려는 값
		int left = 0;
		int right = arr.length - 1;
		int mid;

		while (left <= right) {
			mid = (left + right) / 2;
			if (arr[mid] < target) left = mid + 1;
			else if (arr[mid] > target) right = mid - 1;
			else return true;
		}
		return false;
	}

2. 재귀

	public static boolean BSearchRecursive(int[] arr, int target, int left, int right) {
		if(left > right) 
        	return false;
		
		int mid = (left + right) / 2;
        
		if (arr[mid] < target) 
        	return BSearchRecursive(arr, target, mid +1, right);
		else if (arr[mid] > target) 
        	return BSearchRecursive(arr, target, left, mid - 1);
		else 
        	return true;
		
	}

 

이분 탐색 시간 복잡도

O(log N)
탐색 범위를 매번 "절반"으로 줄이기 때문

왜 log N인가?

예를 들어 N = 16일 때

16 -> 8 -> 4 -> 2 -> 1 총 4번이면 끝난다.

이것은 2^4 = 16 즉, k번 반복하면 2^k = N이므로 k = log2(N)이다.

 

이분 탐색의 장점

1. 매우 빠르다.
2. 대용량 데이터에 강하다.
3. 매개변수 탐색에 활용 가능하다.

이분 탐색의 단점

1. 반드시 정렬되어 있어야 사용할 수 있다.
2. 배열 구조에서만 효율적이다.