[알고리즘] 검색 알고리즘

이제까지 배운 메모리의 구조, 자료형, 배열과 같은 기본적인 개념을 활용하여 검색이나 정렬과 같은 문제를 푸는 알고리즘을 배울 차례다.

먼저 주어진 배열 속에서 특정 값을 찾는 방법부터 알아보자.

배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조이다.

컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근한다.

만약 어떤 값이 배열 안에 속해 있는지를 찾아 보기 위해서는 배열이 정렬되어 있는지 여부에 따라 아래와 같은 방법들을 사용할 수 있다.

선형 검색

배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사한다.

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

이진 검색

만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복하면 된다.

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

생각해보기

만약 정렬되지 않은 배열이 있다면, 선형 검색과 이진 검색 중 어느것이 빠를까?

정렬되지 않은 상태에서의 이진탐색은 정확하지 않다. 운에따라 빠를 수도, 아예 찾지 못할 수도 있다.

따라서, 정렬되지 않은 배열을 정확하게 검색하는 방법에는 선형탐색이 더 적합하다.