탐색 알고리즘

탐색 알고리즘은 말 그대로 어떤 데이터 구조에서 원하는 값이 있는지 찾아내는 알고리즘이다.

 

선형 탐색 알고리즘

가장 간단한 탐색 방법은 선형 탐색이 있다.

선형 탐색은 데이터 구조를 처음부터 끝까지 하나씩 살펴보는 것을 말한다.

배열이나 리스트같은 선형 데이터 구조에서 사용할 수 있다.

 

예를 들어 다음과 같은 배열이 있다고 하자.

arr = [2, 12, 15, 11, 7, 19, 45]

 

이 배열에서 7이라는 값을 찾으려고 한다.

선형 탐색 알고리즘을 사용하면 배열의 0번 인덱스부터 시작해서 배열의 요소를 하나씩 살펴본다.

위 배열을 0번 인덱스부터 살펴보면 2, 12, 15, 11, 7. 다섯번째 요소에서 원하는 값 7을 찾을 수 있다.

 

이번에는 배열에서 9라는 값을 찾으려고 해보자.

9라는 값은 배열에 없기 때문에 선형 탐색 알고리즘은 배열의 마지막 요소까지 비교 연산을 수행해야한다.

 

배열의 길이가 n이라고 하면 선형 탐색 알고리즘의 시간복잡도는 최선의 경우 O(1)이 된다.(배열의 첫번째 요소가 찾는 값일 경우)

하지만 최악의 경우에는 O(n)이 된다. (배열의 마지막 요소까지 비교했음에도 원하는 값을 찾지 못했을 경우)

평균의 경우에는 O(n)이 된다. (평균적으로 n/2 지점에 있다고 생각할 수 있다)

 

이진 탐색 알고리즘

선형 탐색 알고리즘보다 시간복잡도를 줄일 수 있는 방법이 이진 탐색 알고리즘이다.

이진 탐색 알고리즘은 정렬된 데이터 구조에서만 사용할 수 있다.

정렬된 데이터 구조에서 중앙값을 살펴보면 탐색해야 하는 데이터의 양을 절반으로 줄일 수 있다.

 

예를 들어 다음과 같은 배열이 있다고 생각해보자.

arr = [2, 12, 15, 17, 27, 29, 45]

이 배열은 정렬되어 있으므로 이진 탐색 알고리즘을 적용할 수 있다.

 

이 배열에서 29라는 값을 찾으려고 한다.

배열의 길이는 7이므로 먼저 3번 인덱스의 값을 살펴본다. (7/2 = 3.5이고, 소수점 아래를 버린다)

arr[3]의 값은 17인데, 이 값은 찾으려는 값보다 작다.

배열이 정렬되어 있으므로 arr[3]보다 왼쪽에 있는 값들은 arr[3]의 값보다 작음이 자명하다.

따라서 arr[3]보다 왼쪽에 있는 값들은 비교할 필요가 없어진다.

 

이렇게 한번 비교연산을 수행할때마다 탐색해야 하는 데이터의 양을 절반으로 줄일 수 있다.

 

배열의 길이가 n이라고 했을 때 이진 탐색 알고리즘의 시간복잡도는 최선의 경우 O(1)이 된다. (배열의 중간값이 찾고자 하는 값일 경우)

최악의 경우는 O(logN)이 된다.

평균적인 경우라도 O(logN)이 된다.