[algorithm] 이진탐색(Binary Search)

이진탐색

정렬된 배열 또는 리스트에 적합한 고속 탐색 방법

• 배열의 중앙값을 조사하여 찾고자 하는 항목이 왼쪽, 혹은 오른쪽 부분 배열에 있는지 알아내어 탐색의 범위를 반으로 줄인다.

• 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요 없다.

• 정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘이다.
  이 알고리즘은 배열을 반복적으로 반으로 나누어 찾고자 하는 값이 어느 부분에 있을지 좁혀나가는 방식으로 작동한다.
  

시간복잡도

• 𝑂(log𝑛)

이진탐색의 성능

• 이진탐색은 탐색을 반복할 떄 마다 탐색범위가 반으로 준다.
  탐색 범위를 더 이상 줄일 수 없는 1이 될 때의 탐색횟수를 k라고 한다면,

탐색 횟수	배열 길이
1	n/2
2	n/4
3	n/8
...	...
k	n/2^k

배열 길이가 1이 될 때 더이상 쪼갤 수 없다.

즉, n/2^k = 1 을 만족한다.
K에 관해 정리한다면, k = log 2 n이다.
따라서, 𝑂(log 2 𝑛) = 𝑂(log𝑛) 이므로 이진탐색은 𝑂(log𝑛) 의 시간복잡도를 가진다.

이진탐색의 구현

1. 초기설정

• 배열이 정렬되어 있어야 한다.

• 시작점(low), 중간점(mid), 끝점(high) 설정

• 즉 어떤 시점에서 탐색되어야 할 범위는 low부터 high까지가 된다.

2. mid값 계산

• mid = (low + high) / 2

3. array[mid] 값과 구하고자 하는 key값을 비교한다.

• key > mid : 구하고자 하는 값이 중간값보다 높다면 low = mid + 1 (왼쪽 반을 버림)

• key < mid : 구하고자하는 값이 중간값 보다 낮다면 high = mid - 1(오른쪽 반을 버림)

• key == mid : 구하고자 하는 값을 찾음, 해당 인덱스를 반환

  4. low > high가 될 때 까지 위의 1~3번을 반복

code_재귀함수호출

int binarySearch1(int key, int low, int high) {
	int mid;

	if(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) { // 탐색 성공 
			return mid;
		} else if(key < arr[mid]) {
			// 왼쪽 부분 arr[0]부터 arr[mid-1]에서의 탐색 
			return binarySearch1(key ,low, mid-1);  
		} else {
			// 오른쪽 부분 - arr[mid+1]부터 arr[high]에서의 탐색 
			return binarySearch1(key, mid+1, high); 
		}
	}

	return -1; // 탐색 실패 
}

반복을 이용한 이진 탐색 구현

반복 구조를 사용하는 것이 재귀 호출로 구현하는 것 보다 효율적이다.

code_반복구조

int binarySearch2(int key, int low, int high) {
	int mid;

	while(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) {
			return mid;
		} else if(key < arr[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return -1; // 탐색 실패