탐색 알고리즘 (선형, 이진, 해시)

탐색 알고리즘

원하는 값을 검색하기 위한 알고리즘이다.

선형 탐색 알고리즘 (Linear Search Algorithm)

탐색 알고리즘 중 가장 간단한 알고리즘이다. 처음부터 원하는 값이 나올 때까지 하나하나 살펴보는 방법이다.
최악의 경우는 원하는 값이 가장 마지막에 있을 경우이며 O(n) 의 시간복잡도를 갖는다.

...

이진 탐색 알고리즘 (Binary Search Algorithm)

배열의 중앙에 있는 값을 목표한 값과 비교하여 중앙값의 왼쪽 구간 또는 오른쪽 구간을 검색 범위로 정한다. 정렬된 리스트에서 사용한다. 최악의 경우 시간복잡도는 O(logN)이다.

해시 탐색 알고리즘 (Hash Search Algorithm)

해시함수를 이용하여 계산된 해시값을 인덱스로 사용하는 방법이다. 데이터와 index를 연결시켜 검색이 매우 빠르다. 시간복잡도는 항상 O(1)이다. 계산된 해시값이 같은 '해시충돌'이 일어날 수 있다.

해시함수가 10으로 나눈 나머지라고 할 때, 해시 탐색 알고리즘을 이용한 탐색 과정은 다음과 같다. 해시충돌이 일어날 우려가 있으므로, 해시값이 적절하게 분배되도록 해시함수를 만들어야 한다.