선형 구조의 탐색

선형 구조의 탐색

이번 글은 선형 구조란 무엇이고 선형 구조 속에서 탐색하는 대표적인 방법 2가지를 설명한다.

 

선형 구조란?

선형 구조란 프로그래밍 언어를 배울 때 배우는 배열, 연결 리스트 같은 말 그대로 선 같이 생긴 데이터 구조를 선형 구조라고 한다.

 

반대로 비선형 구조는 트리, 그래프 등이 있다.

 

[배열] - 대표적인 선형 구조

[연결 리스트] - 얘도 선형 구조다.

 

선형 탐색

선형 탐색에는 대표적으로 전체 탐색과 이분 탐색(이진 탐색)이 있다.

전체 탐색은 말 그대로 전체를 순환해서 어떠한 값을 찾는 것을 말하고 이분 탐색은 정렬된 선형 구조에서 부분적으로만 탐색을 해서 값을 찾는 부분 탐색을 말한다.

 

구체적인 예시와 설명을 보면서 설명하면 좋을 것 같다.

전체 탐색

전체 탐색은 전체를 순환하기 때문에 시간 복잡도가 O(n)이다. 실제 코드를 보고 이해하면 될 것 같다.

 

이분 탐색

이분 탐색은 정렬이 되어 있는 상태에서 유용하게 사용할 수 있는데 반을 잘라서 계속 보는 것이다.

 

예시를 들어서 설명하겠다. 크기가 10인 배열이 있을 때(인덱스는 [0, 9]이다.)

 

이렇게 단 3번 만에 찾을 수 있다. 이분 탐색은 반씩 쪼개서 탐색하기 때문에 시간 복잡도가 O(log2 n)이다.

정리를 하자면 이분 탐색의 작동 원리는 이렇다. pseudo code라고 하기엔 뭐하지만 코드에 익숙해지는 것이 중요하다고 생각한다.

while (left <= right)
{
    mid = (left + right) / 2;
    if (array[mid] == find)
        return mid;
    else
    {
        if (array[mid] > find)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

	#include <stdio.h>
	/*
	* if(찾으면) 위치를 출력
	* else -1 출력
	*/
	int BinarySearch(int* array, int left, int right, int find)
	{
	while (left <= right)
	{
	int mid = (left + right) / 2;
	if (array[mid] == find)
	return mid;
	else {
	if (array[mid] > find)
	right = mid - 1;
	else
	left = mid + 1;
	}
	}
	return -1;
	}
	int main()
	{
	int List[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	const int FIND = 7;
	int ans = BinarySearch(List, 0, 10, FIND);
	if (ans == -1)
	printf("Not Found\n");
	else
	printf("Found: %d\n", ans);
	return 0;
	}

view raw BinarySearch.c hosted with ❤ by GitHub