탐색 알고리즘은 여러 가지가 있습니다.
선형 탐색(LinearSearch)과 이진 탐색(BinarySearch)을 함수로 구현해보도록 하겠습니다.

---

1) 선형 탐색

LinearSearch, 순차 탐색이라고도 불리는 선형 탐색은 말 그대로 직선상에서 값을 찾는다고 보시면 됩니다.
이것을 가능하게 하는 LinearSearch 함수를 구현해보겠습니다.

선형 탐색 알고리즘 구현

#include <stdio.h>

LinearSearch(int *a, int len, int val) {

	for(int i=0; i<len; i++)
    	if(a[i]==val) return i
 
    return -1;
}

위 함수는 데이터 집합 a와 그것의 데이터 개수인 len 그리고 찾으려는 값 val을 받습니다.
그리고 a의 0번째 데이터부터 1번째, 2번째... 마지막까지 데이터 값을 차례대로 훑어가면서 val인지 아닌지를 판별합니다.
val을 찾는데에 성공했다면 그것의 위치를 반환합니다.
아니라면 -1를 반환하게 됩니다.

시간복잡도

선형 탐색 알고리즘의 시간복잡도는 O(N)입니다.
가장 최악의 경우는 찾으려는 값이 탐색 방향 기준 마지막에 있거나, 데이터 집합에 존재하지 않는 경우인데요.
그럴 경우에는 데이터 집합의 모든 원소들을 탐색해야 하기 때문에 O(N)이 되는 것입니다.

2) 이진 탐색

BinarySearch라고 불리는 이진탐색은 쉽게 말하면 반 씩 나누어 값을 탐색하는 것입니다.
흔히 업다운 게임을 할 때 많이 쓰이는 탐색 방법이죠.
BinarySearch 함수를 구현해보겠습니다.

이진 탐색 알고리즘 구현

#include <stdio.h>

BinarySearch(int *a, int len, int val) {

    int first = 0;
    int last = len-1;
    int mid;
    
    while( first <= last ) {
    
    	mid = (first+last)/2;
        
    	if(a[mid] == val) {
			return mid;
		}
		else {
			if(a[mid] > val)
				last = mid - 1;
			else
				first = mid + 1;	
		}
        
    }
    
    return -1;
}

이진 탐색은 탐색하려는 범위를 제외시키면서 값을 찾는 탐색 알고리즘이라고도 할 수 있습니다.

• first : 유효한 탐색 데이터 범위의 시작
• last : 유효한 탐색 데이터 범위의 끝
• mid : 현재 탐색하고 있는 데이터 위치 (first + last) / 2

먼저 mid를 first와 last 사이의 중간값으로 조정합니다.
a[mid]==val 가 참인지 거짓인지를 판별합니다.
맞다면 현재 인덱스 위치를 반환하고 (mid)
아니라면
1. a[mid] > val 인 경우
 - last를 mid-1로 조정합니다.
2. a[mid] < val 인 경우
 - first를 mid+1로 조정합니다.

앞에서 소개해드린 선형 탐색보다는 어쩌면 빠른 탐색 방법이지만 데이터가 정렬되어 있어야 한다는 전제조건이 있습니다.

시간복잡도

이진 탐색 알고리즘의 시간복잡도는 O(log N)인데요.
반 씩 나누어 탐색을 하기 때문입니다.
따라서 최악의 경우 log N의 시간이 걸립니다.

3) 선형 탐색 VS 이진 탐색

그러면 선형 탐색과 이진 탐색 중 어떤 탐색 알고리즘이 더 좋을까요?

찾으려는 값이 첫번째 위치에 있다면,
선형 탐색의 경우에는 바로 찾을 수 있을 것입니다.
반면에 이진 탐색의 경우에는 log N의 시간이 걸리죠.

반대로 찾으려는 값이 가운데 mid의 위치에 있다면,
이진 탐색의 경우 바로 찾을 수 있을 테지만
선형 탐색의 경우에는 N/2의 시간이 걸리겠죠.

사실 더 좋은 알고리즘이란 없고 상황에 따라 다를 뿐입니다.
주어진 상황에 따라 더 효율적인 알고리즘을 선택하시길 바랍니다!