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

❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.

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

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

선형 검색

배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사합니다.
아래 의사코드와 같이 나타낼 수 있습니다.

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

생각해보기

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

• 선형 검색이 빠릅니다.
  • 선형검색은 O(N)이지만
  • 정렬되지 않은 배열에서의 이진 검색은 정렬을 한 뒤에 검색을 해야하기 때문에 O(NlogN) + a 입니다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기