[알고리즘] 순차탐색, 이진탐색 알고리즘 소개 및 성능 비교

1. #include <a_samp>
2.  
3. stock LinearSearch( arr[], size, target )
4. {
5.         new i;
6.        
7.         for( i = 0; i < size; i++ ) {
8.                 if( arr[i] == target ) {
9.                         printf("배열의 길이가 %d일 때 순차탐색 알고리즘의 연산 횟수 : %d", size, i);
10.                         return i;
11.                 }
12.         }
13.        
14.         return -1;     
15. }
16.  
17. stock BinarySearch( arr[], size, target )
18. {
19.         new first = 0, mid, last = size-1;
20.         new count;
21.        
22.         while( first <= last ) {
23.                 mid = (first+last)/2;
24.                 count++;
25.  
26.                 if( target == arr[mid] ) {
27.                         printf("배열의 길이가 %d일 때 이진탐색 알고리즘의 연산 횟수 : %d", size, count);     
28.                        return mid;
29.                 }
30.                 else {
31.                         if( target < arr[mid] )
32.                             last = mid-1;
33.                         else
34.                             first = mid+1;
35.                 }
36.         }
37.  
38.         return -1;
39. }
40.  
41. main()
42. {
43.         new
44.                 arr1[100] = {0, },
45.                 arr2[1000] = {0, }
46.         ;
47.         new idx;
48.        
49.         arr1[99] = arr2[999] = 77777;
50.  
51.         idx = LinearSearch(arr1, sizeof(arr1), 77777);
52.         printf("arr1 배열에 77777이 위치한 인덱스 : %d", idx);
53.         idx = BinarySearch(arr1, sizeof(arr1), 77777);
54.         printf("arr1 배열에 77777이 위치한 인덱스 : %d", idx);
55.        
56.         idx = LinearSearch(arr2, sizeof(arr2), 77777);
57.         printf("arr2 배열에 77777이 위치한 인덱스 : %d", idx);
58.         idx = BinarySearch(arr2, sizeof(arr2), 77777);
59.         printf("arr2 배열에 77777이 위치한 인덱스 : %d", idx);
60. }

배열의 크기를 조금 더 늘렸다면 차이가 눈에 확 들어오실텐데,

배열의 길이가 어느 정도 초과하게 되면 구동기에서 런타임 에러가 발생하네요.

순차탐색 알고리즘은 다들 한번씩은 구현해본 경험이 있어서 눈에 익으실텐데,

이진탐색 알고리즘은 낯선 분들이 많으실 거에요.

순차탐색은 말 그대로 cursor를 배열의 제일 앞 부분부터 시작해서,

target이 발견되지 않을동안 배열의 제일 마지막 위치까지 cursor를 이동시키면서 탐색하는 알고리즘입니다.

이진탐색은 순차탐색과는 달리 전제조건이 필요합니다.

탐색 대상인 데이터들이 정렬되어 있어야 하는데 오름차순 정렬이면 이진탐색 알고리즘도 오름차순 기준으로 맞추어야 합니다.

이진탐색 알고리즘은 loop를 돌 때마다 탐색 대상이 하나씩 줄어드는 순차탐색 알고리즘과는 달리 반씩 줄어듭니다.

이것이 이진탐색 알고리즘이 순차탐색 알고리즘에 비해, 많은 양의 데이터를 처리할 때 연산 횟수를 줄일 수 있는 이유입니다.