선형 탐색과 이진 탐색

⊙ 선형 탐색과 이진 탐색의 탐색 방법을 안다.
⊙ 선형 탐색과 이진 탐색의 각각 유리한 상황을 이해한다.
⊙ 이진 탐색을 구현한다.

 

선형 탐색

선형 탐색이란 정보를 앞에서부터 순서대로 찾는 것을 의미한다. 찾아봐야 하는 자료가 정돈되어 있지 않고 아무런 특징을 발견할 수 없을 때 사용하는 탐색이다. 제작하기 쉽다는 장점이 있지만 찾는 자료가 뒷부분에 있다면 오랜시간을 기다려야 한다는 단점이 있다. 정말 앞에서부터 차례대로 찾는값이 맞는지 확인하는거라 따로 탐색 방법이 이해하기 어렵거나 하지는 않을 것이다.

 

---

 

이진 탐색

이진 탐색이란 정렬된 데이터가 있다면 탐색해야하는 자료의 중간값을 찾아 정보를 탐색해가는 방식을 의미한다. 중간값을 판단해서 검색의 범위를 줄여 나가는 방식이기 때문에 모든 값을 다 검사하지 않는다. 그래서 선형 탐색보다 빠르게 탐색할 수 있다.

중요한 건 우리가 탐색해야하는 자료가 정리 되어 있는 경우 유리하게 사용할 수 있는 정렬이라는 것이다. 즉, 자료가 정렬 되어 있어야만 사용할 수 있다는 단점을 가진다는 뜻이다. 하지만 자료의 양이 많을 수록 빠른 결과가 나온다는 장점이 있다.

시간 복잡도:
최악 및 평균 = O(log n)
최선 = O(1)
*n = 데이터 수

동작 원리

선형 탐색과 다르게 중간값을 뽑아서 어쩌구 하는걸 보면 뭔가 과정을 이해할 필요가 있겠다는 생각이 든다.

정렬된 데이터 속에서 15를 찾는다고 생각해보자. min과 max는 각각 가장 처음과 가장 끝을 말한다. 여기서는 0이 min, 7이 max이다. 먼저 중앙값을 찾는다. min+(max-min)/2를 계산하면 가운데 값의 인덱스가 나오게 된다. 처음 상태에서 중간값을 계산하면 0+(7-0)/2=3이므로 3번째 있는 수를 중간값으로 한다. 중간값이 계산되면 중간값이 우리가 찾는 15가 맞는지 확인한다. 3번째 있는 수는 9로 15가 아니다. 그리고 15보다 작은 수이다. 따라서 우리가 찾는 15를 찾기 위해서는 더 뒤로 가야한다.

 

이제 9앞에 수는 볼 필요가 없기 때문에 min을 mid 다음의 수로 옮겨 온다. 만약 우리가 찾는 수가 9보다 작았다면 max를 mid의 앞으로 가져오면 된다. 즉 mid-1을 하면 되는 것이다. 지금으로 다시 돌아와서 mid+1을 하여 5번째 수를 min으로 한다. 바뀐 mid를 가지고 다시 중간값을 구해준다. 다시 중값을 구하면 4+(7-4)/2=5이다. 5번째 값을 까서 확인해보니 13이다. 13은 15가 아니고 15보다 작은 수다. 따라서 한번 더 뒤로 가야한다.

 

min을 mid의 뒤로 옮기니 6번째 숫자가 되었다. 다시 중간값을 구한다. 6+(7-6)/2=6이므로 6번째 숫자가 중간값이 된다. 중간값을 비교해보니 우리가 찾던 15가 맞다. 이렇게 원하는 수를 찾는 것이다.

1.  

그럼 만약 내가 가진 데이터 속에 찾는 값이 없다면 어떻게 되는 걸까? 만약 내가 원하는 수가 16이었다고 생각해보자. 마지막 순간으로 돌아가 mid는 15이기 때문에 찾았다가 아니라 내가 찾는 16과 다르다 였다면? 15는 16보다 작은 수다. 16을 찾기 위해서는 더 뒤로 가야한다. 다시 min을 mid의 다음수로 만든다. 이제 min은 7이 되었다. 그러면 min과 max가 모두 7이고 mid도 7이될 것이다. 이제 7번째 수를 까보니 20이다. 16보다 큰 수다. 16보다 큰 수가 나왔으니 앞을 봐야한다. 그래서 max를 mid의 앞으로 옮겨준다. 그러면 max는 6번째 수를 가리키게 된다. 어라 이러면 min과 max가 교차하게 된다. 그렇다. min과 max가 교차하는 순간 바로 이 데이터에는 내가 찾는 수가 없다는 것을 알 수 있다.

 

중간값을 구하는 방법

중간값을 구하는 방법은 두가지가 있다. 첫 번째로 위의 예제를 설명하면서 사용한 방법이다.

mid=min+(max-min)/2

이 방법으로 중간값을 구하면 효율적이지는 못하지만 이 다음에 소개할 방법에서 생기는 오버플로우 문제에서 자유로워 진다. 

 

두 번째 방법은 보통 중간값을 구한다고 하면 먼저 생각나는 방법이다.

mid=(max+min)/2

이 방법에서 생기는 문제는 max+min이 원인이다. 만약 int형 변수인 mid에서 max+min이 int형 변수의 범위를 넘어가는 순간 오버플로우가 발생할 것이고 그러면 max+min은 음수로 계산이 된다. 이런 문제가 있지만 max와 min의 범위가 그렇지 않다면 이 방법이 좀 더 효율적이다.

 

오버플로우가 발생할 값을 다룬다면 첫 번째 방법을 사용하고 그렇지 않다면 두 번째 방법을 사용하면 된다.

 

이진 탐색 구현하기

이제 이진탐색을 직접 구현해보자.

#include <iostream>
using namespace std;

int main()
{
	int myArray[] = { 1, 6, 8, 9, 12, 13, 15, 20 };

	// 찾는 숫자
	int findNum;
	cout << "찾는 숫자를 입력하세요: ";
	cin >> findNum;

	int min = 0;
	int max = 7;
	int mid = 0;

	while (min <= max)
	{
		mid = min + (max - min) / 2;
		if (myArray[mid] == findNum)
		{
			cout << mid << "번째에서 " << findNum << "을 찾았습니다!!" << endl;
			return 0;
		}
		else if (myArray[mid] < findNum)
		{
			min = mid + 1;
		}
		else if (myArray[mid] > findNum)
		{
			max = mid - 1;
		}
	}

	cout << findNum << "은 존재하지 않습니다." << endl;
	return 0;
}

while 반복문의 조건 정도만 헷갈리지 나머지는 어렵지 않게 원리를 이해하면 구현할 수 있다.

min<=max는 min과 max가 엇갈리지 않을 동안은 계속 반복이라는 뜻이다. 따라서 min>max가 되면 반복문이 종료되는 것이다. 반복문이 종료되었다는 것은 findNum이 존재하지 않는 것이기 때문에 존재하지 않는다는 출력을 하게 하였다.

 

 

선형 탐색과 이진 탐색의 활용 상황

선형 탐색은 차례대로 자료를 모두 검사하기 때문에 아래의 경우 활용할 수 있다.

• 데이터의 양이 적을 경우
• 데이터에 정리할 수 있는 패턴이 보이지 않는 경우

이진 탐색은 모든 데이터를 검사하지 않아 빠르게 탐색할 수 있기 때문에 아래의 경우 활용할 수 있다.

• 데이터의 양이 많은 경우
• 데이터가 정렬할 수 있는 패턴을 파악할 수 있는 데이터일 경우

 

---

 

배운 내용 정리

• 선형 탐색은 정보를 앞에서부터 순서대로 찾는 방식을 말한다.
• 이진 탐색은 정렬된 데이터를 자료의 중간값을 찾아 정보를 탐색해가는 방식을 말한다.
• 선형탐색은 정렬되지 않아도 데이터를 탐색할 수 있지만 이진 탐색은 정렬되어 있어야 데이터를 탐색할 수 있다.
• 이진 탐색은 모든 데이터를 보는 것이 아니기 때문에 효율이 더 좋다.
• 이진 탐색을 구현할 때 중간값을 구하는 방법은 두 가지이며 오버플로우가 일어나는 상황을 확인한 후 선택하면 된다.