탐색 알고리즘 (검색 알고리즘: 선형검색과 이진검색)

목차

---

• 탐색 알고리즘이란
• 선형 검색이란
• C언어로 선형 검색을 구현한 코드
• 이진 검색이란
• C언어로 이진 검색을 구현한 코드
• 선형 검색과 이진 검색의 시간복잡도

 

 

탐색 알고리즘 이란?

---

탐색 알고리즘이란 수많은 데이터들 사이에서 원하는 데이터를 찾는 알고리즘이다.

실제로 검색 엔진에 탐색 알고리즘이 많이 사용되기도 한다.

그래서 탐색 알고리즘을 검색 알고리즘이라고 부르기도 한다.

오늘은 탐색 알고리즘 중 선형 검색과 이진 검색에 대한 내용을 다룰 것 이다.

 

 

선형 검색 이란?

---

선형 검색 알고리즘 이미지화

선형 검색은 위의 그림처럼, 가장 좌측부터 우측까지 순서대로 원하는 데이터를 찾아보는 알고리즘이다.

즉 첫 번째부터 끝까지 하나하나 확인하는 알고리즘이다.

선형 검색은 배열이 정렬되어 있지 않던, 정렬되어 있던 이용할 수 있다.

하지만 하나하나 찾아보는 것이기 때문에, 많은 시간이 소요되서 잘 사용하지 않는 알고리즘이다.

 

 

C언어로 선형 검색을 구현한 코드

---

소스 코드

#include <stdio.h>


int Linear_Search(int arr[], int count, int num);


int main() {

	int Array[10] = { 1,3,5,6,32,1,7,10, 645,2 };	
	Linear_Search(Array, sizeof(Array) / sizeof(int), 10);


	return 0;
}



/*
Linear_Search 함수 설명
1. arr[]은 배열, count는 배열의 길이, num은 검색할 숫자
2. 검색한 숫자가 존재하면, 배열의 인덱스 출력
3. 검색한 숫자가 존재하지 않으면, 숫자가 존재하지 않음을 출력
*/

int Linear_Search(int arr[], int count ,int num) {

	for (int i = 0; i < count; i++) {
		if (arr[i] == num) {
			printf("검색한 숫자는 %d번째에 있습니다.\n", i+1);
			return 0;
		}
	}

	printf("검색한 숫자가 배열에 존재하지 않습니다.\n");
	return -1;
}

 

 

이진 검색 이란?

---

이진 검색 알고리즘 이미지화

이진 검색은 반씩 나눠서 검색하는 것을 반복하는 알고리즘이다.

이진검색은 정렬된 배열에서 주로 사용된다.

 

위의 이미지를 이용해서 이진 검색에 대해 설명해 보자면, 

우리는 위의 배열에서 76이란 숫자를 찾을 것이다.

첫번째, 가운데 숫자가 76보다 큰지 작은지 확인한다.

두번째, 가운데 숫자인 47이 76보다 작으므로, 47의 오른쪽 배열을 탐색할 것이다.

세번째, 47의 오른쪽 배열의 가운데 숫자가 76보다 큰지 작은지 확인한다.

네번째, 가운데 숫자인 77이 76보다 크므로, 77의 왼쪽 배열을 탐색할 것이다.

다섯번째, 77의 왼쪽 배열의 가운데 숫자가 76보다 큰지 작은지 확인한다.

여섯번째, 가운데 숫자인 64는 76보다 크므로, 64의 오른쪽 배열을 탐색할 것이다.

일곱번째, 64의 오른쪽 배열의 가운데 숫자는 76이다. 탐색 끝!

 

 

C언어로 이진 검색을 구현한 코드

---

소스 코드

#include <stdio.h>

int Binary_Search(int arr[], int count, int num);


int main() {

	int Array[10] = { 1,2,3,4,5,6,7,8,9,10 };
	Binary_Search(Array, sizeof(Array) / sizeof(int), 11);

	return 0;
}


/*
Binary_Search 함수 설명
1. arr[]은 배열, count는 배열의 길이, num은 검색할 숫자
2. 검색한 숫자가 존재하면, 배열의 인덱스 출력
3. 검색한 숫자가 존재하지 않으면, 숫자가 존재하지 않음을 출력
*/

int Binary_Search(int arr[], int count, int num) {
	
	if (num < arr[0] || num > arr[count - 1]) {
		printf("검색한 숫자는 배열에 존재하지 않습니다. \n");
		return -1;
	}


	int left = 0;
	int right = count - 1;
	int mid;

	while (left<=right) {

		mid = (left + right) / 2;

		if (arr[mid] == num) {
			printf("검색한 숫자는 배열의 %d번째에 존재합니다.\n", mid+1);
			return 0;
		}

		if (arr[mid] < num) {
			left = mid+1;
		}
		else {
			right = mid-1;
		}

	}

}

 

 

선형 검색과 이진 검색의 시간 복잡도

---

Big-O (빅-오)

Big-O 종류	의미	예시
O(2ⁿ)	n개를 입력했을 때, 최악의 경우 2ⁿ번 실행된다.
O(n³)	n개를 입력했을 때, 최악의 경우 n³번 실행된다.
O(n²)	n개를 입력했을 때, 최악의 경우 n²번 실행된다.
O(n log n)	n개를 입력했을 때, 최악의 경우 n log n번 실행된다.
O(n)	n개를 입력했을 때, 최악의 경우 n번 실행된다.	선형 검색
O(log n)	n개를 입력했을 때, 최악의 경우 log n번 실행된다.	이진 검색
O(1)	n개를 입력했을 때, 최악의 경우 1번 실행된다.

 

Big-Ω (빅-오메가)

Big-Ω 종류	의미	예시
Ω(2ⁿ)	n개를 입력했을 때, 최선의 경우 2ⁿ번 실행된다.
Ω(n³)	n개를 입력했을 때, 최선의 경우 n³번 실행된다.
Ω(n²)	n개를 입력했을 때, 최선의 경우 n²번 실행된다.
Ω(n log n)	n개를 입력했을 때, 최선의 경우 n log n번 실행된다.
Ω(n)	n개를 입력했을 때, 최선의 경우 n번 실행된다.
Ω(log n)	n개를 입력했을 때, 최선의 경우 log n번 실행된다.
Ω(1)	n개를 입력했을 때, 최선의 경우 1번 실행된다.	선형 검색, 이진 검색

 

 

 

---

위 글은 edwith 사이트의 <cs50> 강의 시청과

부스트 코딩 뉴비 챌린지 2020 활동 팀원들과 토론을 통해 공부한 내용을 작성한 것 입니다.

내용상 오류가 있다면 댓글로 적어주세요. 🖐

2020/07/23 - [Life/2020] - [대외활동] 부스트 코딩 뉴비 챌린지 2020

[대외활동] 부스트 코딩 뉴비 챌린지 2020