항해를 진행하면서 프로젝트를 완성하는 것에 쫓기다보니 자료구조와 알고리즘 관련해서 깊게 공부를 할 수 없었다.
프로젝트를 마치고 지금부터라도 하나하나 알아가보려고 한다.
먼저 검색 알고리즘이란 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘이다.
검색 알고리즘에는 선형 검색(Linear Search)과 이진 검색(Binary Search)이 있다.
선형 검색(Linear Search)
- 데이터가 모인 집합(배열, 리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘으로 선형 검색 또는 순차 검색이라고 한다.
| 3 | 4 | 5 | 9 | 7 | 0 | 1 | 6 | 8 | 2 |
|---|
데이터를 정렬하거나 건드릴 필요가 없어 난이도가 쉬운 편이지만 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아진다. 하나하나 모두 비교하기 때문에 비효율적인 단점도 있다.
예로 위와 같은 데이터 집합이 있는 경우 2를 찾으려면 10번의 비교를 해야한다. 만약 100만개, 1,000만개의 데이터가 있고 찾고자 하는 데이터가 100만번째, 1,000만번쨰에 있다면 100만번, 1,000만번 비교를 해야한다.
아래 코드를 보고 조금 더 쉽게 이해해보자.
int LinearSearch(int arr[], int size, int target){
for(int i = 0; i < size; i++)
if(arr[i] == target){
return i;
} 데이터 집합인 arr배열과 배열의 크기(size), 찾는 데이터(target)
1. 반복문을 size만큼 돌리고 배열의 0번 인덱스부터 찾는 값이 있는지 비교를 한다.
2.
| 3 | 4 | 5 | 9 | 7 | 0 | 1 | 6 | 8 | 2 |
|---|
위와 같은 배열이라면 size는 10이고, target은 2가 된다.
3. 반복문을 통해 arr[0] 부터 size만큼 반복문을 돌게될거고 arr[9]에서 target이 되는 2를 찾는다.
4. target을 찾고 해당 인덱스인 9를 리턴한다.
선형 검색은 size에 비례하는 횟수만큼 검색을 실행하기 때문에 시간 복잡도는 O(n)이다.
선형, 순차 검색이 종료되는 조건
1. 찾아야 하는 값을 찾지 못하고 배열의 끝을 지나간 경우
2. 찾아야 하는 값과 같은 요소를 발견한 경우
이진 검색(Binary Search)
- 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘으로 이진 검색은 선형 검색과 다르게 데이터의 집합에서 처음부터 검색하는게 아닌 반으로 나누어 중간값 부터 검색을 하기에 이분 검색이라고도 한다.
위에서 얘기했던 선형 검색은 링크드 리스트에서 자주 쓰이는 반면 이진 검색은 트리 구조에서 자주 쓰이는 형식이다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
선형 검색과 동일하게 10개의 데이터 요소가 있고 이진 검색의 조건으로 정렬을 하였다.
9라는 요소를 찾기 위해 어떤 연산 과정을 거치는지 알아보자.
일단 중간 값인 5와 타켓인 9의 값을 비교한다. 9가 더 큰 숫자이기 때문에 오른쪽으로 진행되며 5보다 작은 0~4까지는 비교 연산을 할 필요가 없다.
다시 5~9까지의 중간값을 다시 선택한다(중간 값인 8 선택)
다시 한번 8과 9를 비교, 9가 더 큰 수이니 왼쪽에 있는 숫자들은 무시하고 남은 한칸에 9가 있다는 것을 찾을 수 있었다.
코드를 보며 조금 더 쉽게 이해해보자.
int BinarySearch(int arr[], int size, int target){
int first = 0;
int last = n - 1;
int mid;
while(first <= last) {
mid = (first + last) / 2;
if(target == arr[mid]){
return mid;
} else if(target < arr[mid]) {
last = mid-1;
} else {
first = mid + 1;
}
}
return -1;
}- first는 arr의 첫번째 인덱스인 0, last는 arr의 마지막 인덱스, mid는 중간값을 뜻한다.
- first가 last가 될때까지 반복문을 돌린다. mid를 중간값으로 정의
- arr의 mid번째에 있는 데이터가 target과 일치한다면 mid를 리턴하고 종료
- 그렇지 않다면 target이 arr[mid] 보다 큰경우와 작은 경우로 나누어 비교를 하며 값을 찾을때까지 범위를 좁혀 나간다.
이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균 겂은 log n 이다. 시간 복잡도는 O(log n) 이다.
이진, 이분 검색이 종료되는 조건
1. arr[mid]와 target값이 일치하는 경우
2. 검색 범위가 더이상 없는 경우
