검색 알고리즘

CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.

---

학습목표

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

핵심 단어

• 선형 검색
• 이진 검색

강의 내용

배열이란 ?

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

어떤 값이 배열에 속해있는지 확인하려면 선형 검색, 이진 검색의 방법을 사용할 수 있다.

1. 선형 검색 (Linear Search)

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

전화번호부를 예로들면 원하는 사람의 번호를 찾기위해 ㄱ ~ ㅎ 까지 순서대로 살펴보는 것이다.

python 코드로 간단하게 나타내면 아래와 같다.

def linear_search(value, array):
    for i in array:
        if i == value:
            return True
    return False

2. 이진 검색 (Binary Search)

이진 검색은 검사하려는 배열이 정렬이 되어있는 경우에만 사용이 가능하다.

배열의 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은 인덱스 또는 큰 인덱스로 이동을 반복하는 방법이다.

python 코드로 간단하게 나타내면 아래와 같다.

def binary_search(value, array):
    first, last = 0, len(array)
    
    while first < last:
        mid = (first+last) // 2
        if value == array[mid]:
            return True
        elif value < array[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return False

생각해보기

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

정렬이 되어있지 않다면 이진 검색은 사용할 수 없다.
이진 검색은 배열의 중간 인덱스를 확인한 후 좌/우 방향을 결정해야 하는데 정렬이 되어있지 않다면 방향 판단 자체가 불가하기 때문이다.

따라서 이 질문에 대한 답은 빠르기에 상관없이 선형 검색을 사용할 수 밖에 없다가 된다.