검색 알고리즘

Intro

우리는 메모리의 구조, 자료형, 배열과 같은 기본적인 개념을 익혔고 이 블로그에선 여태까지 배
운 내용을 활용하여 검색이나 정렬과 같은 문제를 푸는 알고리즘을 배워 보겠습니다.

먼저 주어진 배열 속에서 특정 값을 찾는 방법부터 시작해 보겠습니다.

배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조로 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근합니다.

선형 검색

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

*의사 코드

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