정렬되지 않은 배열에서 선형 검색 vs 이진 검색: 차이점과 효율성

알고리즘을 공부하면서 배열을 검색하는 방법인 선형 검색과 이진 검색에 대해 배우게 된다. 이 두 가지 방법은 각각 장단점이 있는데, 정렬되지 않은 배열에서는 어떤 방법이 더 효율적일까? 지금부터 차근차근 알아보자(:

1. 선형 검색 (Linear Search)

선형 검색은 배열을 처음부터 끝까지 차례대로 하나씩 확인하는 방법이다. 배열이 정렬되지 않아도 사용할 수 있어서, 데이터가 정렬되지 않은 상황에서는 가장 직관적이고 간단한 방법이 된다.
선형 검색의 절차는 다음과 같다:

For i from 0 to n–1
    If i'th element is 50
        Return true
Return false

 
위 코드에서 For i from 0 to n-1은 i라는 변수를 0부터 배열의 마지막 인덱스(n-1)까지 반복한다는 뜻이다. 즉, 배열의 모든 값을 하나씩 확인하는 과정이다. 이때, "i'th element"에서 i'th는 "i번째"라는 뜻이야. 예를 들어, 배열이 [10, 20, 30, 40]일 때, i = 2이면 i'th element는 30이 된다.
 
이 방법은 배열에 속한 모든 요소를 확인하므로 모든 요소를 차례대로 비교하는 방식이다. 배열의 크기가 커질수록 시간이 늘어날 수 있지만, 정렬되지 않은 배열에서는 가장 직관적으로 사용할 수 있는 방법이다.

 

2. 이진 검색 (Binary Search)

이진 검색은 배열이 미리 정렬되어 있을 때만 사용할 수 있는 방법이다. 배열의 중간 값을 기준으로 비교하며, 찾고자 하는 값이 중간 값보다 작은 경우 왼쪽 절반을, 큰 경우 오른쪽 절반을 탐색하는 방식이다.
 
이진 검색의 절차는 다음과 같다.

If no items
    Return false
If middle item is 50
    Return true
Else if 50 < middle item
    Search left half
Else if 50 > middle item
    Search right half

이 방법은 배열을 절반씩 나누어가며 탐색하므로 배열이 정렬되어 있어야만 사용할 수 있다. 이진 검색은 배열이 커져도 탐색 범위가 절반씩 줄어드는 방식이기 때문에 정렬된 배열에서는 매우 빠른 검색 방법이 된다.

 

3. 어떤 방법을 선택할까?

정렬되지 않은 배열에서는 선형 검색이 더 효율적이다. 왜냐하면, 이진 검색은 배열이 정렬되어 있어야만 사용할 수 있지만, 선형 검색은 배열이 정렬되지 않아도 바로 적용할 수 있다. 만약 배열을 이진 검색을 통해 탐색하려면 먼저 배열을 정렬해야 하고, 이 정렬 과정에서 시간이 걸리기 때문에 오히려 선형 검색이 더 빠를 수 있다.
따라서, 정렬되지 않은 배열에서 값을 찾을 때는 선형 검색을 사용하는 것이 가장 적합하다.

4. 의사코드(Pseudocode)란?

여기서 사용된 코드들은 의사코드라고 한다. 의사코드는 알고리즘을 설명할 때 알고리즘의 핵심 흐름만 간단히 표현하는 가짜 코드로, 실제 프로그래밍 언어는 아니다. 의사코드를 사용하는 이유는 알고리즘을 쉽게 이해하고 설명하기 위함이다. 의사코드는 프로그래밍 언어에 구애받지 않기 때문에, 어떤 언어로도 쉽게 변환할 수 있다. 예를 들어, 위에서 본 선형 검색의 의사코드는 C 언어나 Python 등 여러 언어로 바꿀 수 있다.
 
의사코드는 알고리즘을 이해하는 데 도움을 주는 도구로, 실제 코드처럼 문법을 맞추지 않아도 되며 알고리즘의 흐름만을 간단하게 표현하는 것이 목표다.
 

5. 왜 #include <cs50.h> 같은 코드가 없을까?

#include <cs50.h>는 C 언어에서 CS50 강의의 특수한 함수를 사용하기 위해 필요한 코드이다. 예를 들어, 사용자로부터 입력을 받거나 데이터를 처리할 때 사용된다. 그러나 의사코드에서는 실제 프로그래밍 언어의 문법이나 라이브러리 호출 같은 건 포함되지 않는다. 의사코드는 알고리즘의 핵심 흐름을 설명하는 용도로만 사용되기 때문에, 컴퓨터가 실행하는 코드처럼 구체적인 문법은 필요 없다.
 

---

정리되지 않은 배열에서 효율적인 검색 방법

 
정리되지 않은 배열에서 값을 찾을 때는 선형 검색을 사용하는 것이 더 효율적이다. 이진 검색은 배열이 정렬되어야만 사용할 수 있기 때문에, 먼저 배열을 정렬하는 데 드는 시간이 오히려 검색 시간을 늘릴 수 있다. 반면, 선형 검색은 데이터를 정렬하지 않고도 사용할 수 있는 간단한 방법이므로, 정렬되지 않은 배열에서 가장 적합하다🧚🏻.