알고리즘

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

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

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

선형 검색

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

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

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