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

배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조이다.
컴퓨터는 배열 안에 들어있는 내용물 전체를 파악하는 감지 능력이 없다. 
컴퓨터는 이 값들에 접근할 떄 배열의 인덱스 하나하나를 접근한다.

 

검색 알고리즘

• 효율적으로 어떤 값이 배열 안에 속해 있는지 찾아 보기 위해서는 배열이 정렬되어 있는지 여부에 따라 검색 방법이 달라진다.

 

1. 선형 검색

• 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 해당 인덱스의 값을 확인한다.
• 정렬되어 있는지 알지 못하는 상황에서 직접 하나하나 확인하는 방법이다.

 

의사코드

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

 

2. 이진 검색

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

 

의사코드

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

 

think about

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

선형 검색이 빠르다.

이진 검색은 중간값을 기준으로 좌우의 값을 비교하면서 검색을 하기때문에 정렬인 상태에서는 유리하지만 정렬이 되지 않은 상태에서는 의미가 없다.

따라서 차례대로 확인해보는 선형검색이 빠르다. 

 

David J. Malan의 강의

모두를 위한 컴퓨터 과학 (CS50 2019)