1) 검색 알고리즘

• 선형 검색
• 이진 검색

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

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

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

 

선형 검색

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

아래 의사코드와 같이 나타낼 수 있습니다.

 

<의사코드 - sudo code>

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

위의 의사코드에 대한 설명은 50이 리스트에 있는지 없는지 하나씩 순서대로 찾는 것이다.

배열이 정렬되어 있지 않을 때 유용하다.

일반적인 완전탐색이다. 

 

이진 검색

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

아래 의사코드와 같이 나타낼 수 있습니다.

 

<의사코드 - sudo code>

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

위의 의사코드는 절반은 버리면서 하는 코드이다. 

만약에 50이 중간 값이라면 중단하고

중간에 있는 값보다 50이 작다면 왼쪽에 있는 배열만 찾고

중간에 있는 값보다 50이 크다면 오른쪽에 있는 값을 찾는 것이다.