검색 알고리즘

도전하는일반인 2021. 9. 16. 10:26

들어가기 전에

지난시간까지 우리는 메모리의 구조, 자료형, 배열과 같은 기본적인 개념을 익혔습니다. 이번 강의부터는 여태까지 배운 내용을 활용하여 검색이나 정렬과 같은 문제를 푸는 알고리즘을 배워 보겠습니다. 먼저 주어진 배열 속에서 특정 값을 찾는 방법부터 시작해 보겠습니다.

학습 목표

주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있습니다.

핵심 단어

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

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

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

선형 검색

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

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

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

생각해보기

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

나의 생각 : 선형검색이 좀 더 빠를 것 같다.