선형 구조의 탐색

선형 구조의 탐색

이번 글은 선형 구조란 무엇이고 선형 구조 속에서 탐색하는 대표적인 방법 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;
}