자료구조 : 선형검색(Linear Search)와 이진 검색(Binary Search)

검색에 대한 알고리즘 중 선형검색과 이진검색에 대하여 알아보도록 하겠습니다.

선형 검색(Linear Search)

다른이름으로 순차 검색(Sequential Search) 이라고도 하는 선형검색에 대하여 먼저 알아보겠습니다.

선형 검색은 데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘입니다.

→ 순차적으로 검색

3

5

2

1

0

9

7

8

6

4

데이터를 정렬하거나 따로 건드릴 필요가 없고, 난이도가 쉬운 편이나, 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있습니다. 예를들어 위와 같은 데이터의 집합이 있을경우 4를 찾으려면 10번의 비교를 거쳐야 합니다. 100만개의 데이터가 있고 찾고자 하는 데이터가 100만번째에 있다면 100만번의 비교를 해야 한다는 뜻 입니다. 이와 같은 상황을 Worst Case라고 합니다. 관련된 용어로 평균적인 상황을 Average Case 좋은 상황을 Best Case라고 합니다.

코드를 통하여 살펴보도록 하겠습니다.

int LinearSearch(int arr[], int size, int target)
{
    for(int i = 0; i < size; i++)
        if(arr[i] == target) //arr이라는 배열에서 target을 찾는다.
            return i; //찾으면 해당 방번호를 리턴
    return -1; //못찾으면 -1을 리턴
}

주석에 대략적인 설명을 적어드렸지만, 간단한 설명을 조금 더 붙여 보겠습니다.

데이터의 집합인 배열과, 배열의 크기, 찾으려는 데이터(숫자라고 가정)를 함수의 전달인자로 받았습니다.

반복문을 size만큼 실행시킬텐데, 배열의 0번째 방부터 찾는 값이 있는지 훑어 나갑니다. 위 표를 예시로 삼으면 size는 10이고, target은 4가 되겠습니다. 반복문을 통해 arr[0]부터 i의 값을 증가시키면서 진행이 되겠죠. arr[9]에서 target이 되는 4라는 값을 찾았으니, 방의 번호 9를 리턴합니다.

만약 예시와 다르게 target값을 찾지 못했다면 반복문이 종료되어 -1을 리턴하겠죠.

방의 번호를 받고 이제 쓰임새에 따라 쓰면 되겠습니다. 물론 리턴값이 -1일때에 대한 예외처리는 필수.

다음으로 이진검색에 대하여 알아보도록 하겠습니다.

이진검색(Binary Search)

이진검색은 다른말로 이분(二分)검색이라고도 합니다. 반으로 나누어서 연산하기 때문이죠. 선형검색의 경우 데이터 집합의 처음에서 시작하여 끝까지 탐색하는 알고리즘 이지만 이진검색은 중간값부터 탐색을 합니다. 선형검색은 링크드리스트에서 자주 쓰이는 반면에 이진검색은 트리구조에서 자주 쓰이는 형식입니다.

이진검색은 데이터를 계속 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다는 장점을 가지고 있습니다. 그러나 이진검색을 하기 위해서 데이터의 집합이 반드시 정렬(Sort)되어야 한다는 단점이 있습니다. 이렇게 이야기하면 얼마나 빠른지 감이 잘 안올텐데, 예를들어 70억명의 사람중 한사람을 찾으려고 한다면, 선형검색은 Worst Case의 경우 70억번, 대략적으로 생각해도 35억번은 비교연산을 해야 하는데, 이진 검색은 최대 33번의 비교만으로도 원하는 데이터를 찾을 수 있습니다.

0

1

2

3

4

5

6

7

8

9

선형검색과 마찬가지로 10개의 방에 0부터 9까지의 데이터가 담겨 있는 배열입니다. 이야기 했다시피 이진검색의 조건은 데이터가 정렬이 되어있어야 된다는 점이기 때문에, 정렬을 진행했다 가정하고 0부터 9까지 순차적으로 적었습니다. 9라는 데이터를 찾기위해 어떤 연산과정을 거치는지 한번 알아보도록 하겠습니다.

일단 선택된 중간값인 5와 타겟인 9의 값을 비교합니다. 9가 더 큰 숫자이기 때문에 오른쪽으로 진행됩니다. 5보다 작은수인 0부터 4까지는 비교연산을 할 필요가 없습니다. 이제 5부터 9까지의 중간값을 다시 선택합니다.

0

1

2

3

4

5

6

7

8

9

선택된 중간값인 8과 9를 다시 비교합니다. 9가 더 큰수이니 다시 왼쪽 숫자들은 무시되고 남은 한칸에 9가 있다는 것을 알 수 있습니다.

0

1

2

3

4

5

6

7

8

9

코드를 통하여 살펴보도록 하겠습니다.

int BinarySearch(int arr[], int size, int target)
{
    int first = 0;
    int last = n - 1;
    int mid;
 
    while(first <= last)
    {
        mid = (first + last) / 2;
        if(target == arr[mid])
            return mid;
        else if(target < arr[mid])
            last = mid-1;
        else 
            first = mid + 1;
    }
    
    return -1;
}

선형검색과 마찬가지로 데이터의 집합인 배열 arr과 arr의 size가 담긴 int형 변수, target이 되는 값을 전달인자로 받습니다.

함수 내부에서는 로컬변수로 first와 last, mid를 각각 선언 및 초기화 합니다. first는 arr의 첫번째 방을 뜻하는 0으로, last는 arr의 마지막 방인 size - 1 (예를들어 배열의 크기가 10이면 방의 번호는 0부터 9까지 이므로 9가 되겠음), mid는 담을 값이 아직 없으므로 선언만 하고 초기화는 하지 않았습니다.

이제 first가 last가 될때까지 반복문을 실행합니다. 첫줄에 mid를 중간값으로 정의합니다. 이때 arr의 mid번째 방에 있는 데이터가 target과 일치한다면 mid를 리턴하면 종료합니다. 그렇지 않으면 target이 arr[mid]보다 클때와 작을때로 나누어서 비교를 하며, 값을 찾을때까지 범위를 줄여 나갑니다. 선형검색과 마찬가지로 데이터를 찾지 못하면 -1을 리턴하면 되겠습니다.

선형검색과 이진검색에 대하여 알아보았습니다. 도움이 되셨다면 좋겠습니다.