순차탐색이 뭐지? 하고 검색해 들어 온 사람들 대부분은 해당 내용을 보면 매우 실망할 것이다.
왜냐하면 이미 반복문을 배우면서 적어도 한번 이상은 써봤을 탐색 방법이기 때문이다.
2년동안 이 방식으로 검색을 하면서 이 알고리즘의 이름이 순차탐색 이라는 것을 난 오늘 알았다.
매우 단순하다
시간 복잡도: 최악O(n) , 평균 (n+1)/2
시간복잡도가 최악인 경우는 원하는 값이 가장 마지막에 있을 경우이다.
데이터가 배열에 있으면 배열의 처음부터 끝까지 차례대로 비교하면서 원하는
데이터를 찾는 알고리즘이다.
이 알고리즘은 단방향으로 탐색을 하기 때문에 선형탐색(Linear Search)라고 부르기도 한다.
코드는 매우 단순하다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | // for문을 돌면서 데이터를 찾는다. 찾느 데이터가 없는 경우 -1 반환 // 찾는 데이터가 있으면 해당 번째 반환 int search(int dataArr[], int length, int findData) { for(int i = 0; i < length; i++) if (dataArr[i] == findData) return i; return -1; } int main() { int arr[] = {23, 25, 14, 5, 66, 72, 13, 224, 51}; int length = sizeof arr / sizeof arr[0]; int findData = 0; int findIndex = 0; printf("찾으시는 데이터를 입력해주세요: "); scanf("%d", &findData); findIndex = search(arr, length, findData); // if(findIndex == -1) printf("데이터를 찾지 못했습니다.\n"); else printf("데이터는 %d번째에 있습니다.\n", findIndex); return 0; } | cs |
(참조 http://blog.eairship.kr/245 )
순차탐색은 코드구현이 매우 쉬워서 짧은 기리의 데이터를 검색할때 사용하는 것이 좋은 것 같다.
'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글
야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)] (0) | 2016.10.19 |
---|---|
야매 개발자 자료구조 가이드[트리(tree)] (0) | 2016.10.18 |
야매 개발자 알고리즘 가이드[이진 탐색(Binary Search)] (0) | 2016.10.18 |
야매 개발자 알고리즘 퀵 정렬[Quick Sort] (6) | 2016.10.11 |