[알고리즘] 이진탐색, Binary Search | 설계 및 분석, 구현코드

이진탐색 알고리즘이란?

 크기가 n인 정렬된 배열 s에 x가 있는지 결정하는 재귀 알고리즘

 

알고리즘 설계 전략

  배열의 중간에 위치하고 있는 값이 x와 같은 경우 성공을 리턴, 그렇지 않으면 분할(Divide)

  분할(Divide) : 배열을 반으로 나누고, x가 배열의 중간에 있는 값보다 작으면 왼쪽 배열을 선택(오른쪽 배열은 버림), 크면 오른쪽 배열을 선택(왼쪽 배열은 버림).

  정복(Conquer) : 선택한 배열을 갖고 다시 x를 찾는다.

 

알고리즘 수도 코드

 

index location (index low, index high) {
  index mid;
    
  if(low > high)
    return 0;
  else {
    mid = ⌊(low+high) / 2⌋; 	//배열 가운데 값을 구함
    if (x == s[mid]) 	// x가 mid값과 같은 경우 성공 리턴, ①
      return mid;
    else if (x < s[mid]) 	// 분할, x가 mid보다 작은 경우 왼쪽 배열 선택, ② 
      return location(low, mid-1); 	//정복
    else 	// 분할, x가 mid보다 큰 경우 오른쪽 배열 선택, ③
      return location(mid+1, high); 	//정복
  }
}

 

알고리즘 성능 분석

  이제 알고리즘의 성능을 분석해보자. 재귀 호출이 있는 경우 분석하는 방법은 다음과 같다.

<재귀 호출이 있는 알고리즘의 성능 분석 방법>
① 복잡도 함수의 점화식 수립한다.
② 수립한 점화식을 일반화한다.

 ① 복잡도 함수의 점화식 수립

 basic operation : x 와 배열 s의 중간 값과의 비교(위 코드 ①, ②, ③)

즉, 배열 중간 값이 찾고자하는 x인지 비교하는 부분을 단위연산 1회로 간주한다.

binary search의 worst-case를 구해보자.

 

  어떤 경우가 worst-case, 즉 basic operation이 가장 많이 발생할까? 찾고자 하는 값이 배열의 가장 왼쪽에 있거나, 가장 오른쪽에 있거나, 혹은 없을 때이다. x값을 찾기위해 계속 배열을 쪼개는데 이렇게 맨 끝에 있거나 아예 없을 경우 배열을 쪼개야하는 횟수가 제일 많기 때문이다. 

 

  점화식을 수립하기 위해 n=8이고, 8이 배열의 맨 끝에 있다고 가정해보자. 이 경우 아래의 그림과 같이 최악의 경우(=배열 맨 끝에 있는 경우) 총 4번 방문한다.

 

 

  n=16일 경우, 16은 8의 2배이므로 방문 횟수도 2배 늘어나 8번이 될 것같지만, n=16이면 최악의 경우 총 5번 방문한다.

  즉, n이 2배가 됐을 때 방문횟수는 1만큼 늘어난다. 배열 길이가 2배가 되어도, 분할(Divide)과정에서 왼쪽배열, 오른쪽 배열로 나뉜 후 이 두 배열 중 하나만 선택되고 나머지 하나는 버려지기 때문이다. 선택된 반쪽짜리 배열에서는 다시, n=8인 배열, 즉 위에서 다뤘던 경우만큼의 방문횟수가 발생한다. 따라서 k≥0이고, n=2^k라 할 때 w(n) = k + 1이다. 

 

n	w(n)
8(=23)	4
16(=24)	5
32(=25)	6
.   .   .
2k	k+1

∴ n=2^k라 할 때(k≥0) w(n) = k + 1

 

  best-case인 경우는 언제일까? 찾고자 하는 값 x가 바로 배열의 중간에 있을 때이다. 이 때에도 가운데 값이 찾고자하는 값 x인지 비교하는 과정이 한번은 무조건 일어나야하므로, b(n)=1이다.

∴ b(n)=1

 

 ② 점화식 일반화

w(1) = 1

w(2) = 2

w(4) = 3

w(8) = 4

...

w(2k) = k + 1

w(2^k) =k + 1을 n에 대한 식으로 나타내면 n=2^k라고 가정했으므로 log n = k이다.

∴ w(2^{log n}) = log n + 1 ∈ O(log n)

 

 

구현코드

#include <iostream>
using namespace std;

int location(int first, int last);

int x;
int s[100000];

int main(void)
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> s[i];
	cin >> x;

	cout << location(0, n - 1) << endl;
	cout << cnt << endl;
	
}

int location(int first, int last)
{
	int mid;

	if (first > last)
		return -1;
	else
	{
		mid = (first + last) / 2;

		if (x == s[mid])
			return mid;
		else if (x < s[mid])
			return location(first, mid - 1);
		else
			return location(mid+1, last);
	}
}