탐색 알고리즘

[1, 2, 3, 4, 5, 6, 7]

이렇게 정렬되어 있는 리스트가 있다. 리스트 안에서 특정 값을 찾는 방법은 무엇이 있을까?

어떤 방법으로 푸느냐에 따라 걸리는 시간이 달라질텐데 이런 다양한 방법을 고민하고 어떤 방법이 좋을지 고민하는 것이 알고리즘 공부입니다.

먼저 순서대로 하나씩 찾아가는 방법이 있을 것이다. 이것을 선형 탐색 알고리즘(linear search algorithm)이라고 합니다.

또 다른 방법으로는 중간에 하나의 숫자를 찾는다. 그리고 왼쪽에 있는지 오른쪽에 있는지 판단하며 반씩 줄여간다. 이를 이진 탐색 알고리즘(binary search algorithm)이라고 합니다.

위 두 가지의 탐색 알고리즘은 리스트의 크기가 작을 때는 크게 체감할 수 없지만 커질수록 더 차이를 느끼게 됩니다. 예를 들어 21년 기준 27억명의 페이스북 유저에서 특정 유저를 검색한다고 했을 때 선형 탐색의 최악의 경우 27억명의 유저를 검색해야 하지만 이진 탐색의 최악의 경우는 31명의 유저를 검색하면 됩니다.

이렇듯 이진 탐색의 경우가 리스트의 크기가 커질 수록 효율이 좋지만 항상 그런 것은 아닙니다. 리스트가 정렬되어 있지 않다면 이진 탐색이 불가하기 때문입니다.