지난 글: [알고리즘] - 퀵 정렬
선형 탐색은 배열에서 데이터를 탐색하는 알고리즘이다. '배열'에 대해서는 이전에 작성한 [알고리즘] - 배열에 상세히 설명하고 있다. 바로 다음에 배울 이진 탐색과 달리 데이터가 마구잡이로 나열돼 있어도 적용할 수 있다. 작업은 단순해서 배열의 앞에서부터 순서대로 데이터를 확인하면 된다. 저장되는 데이터는 아무 것이나 상관없지만 여기서는 잘 이해하기 위해 정수가 저장된 경우를 가정한다.
1
3 9 8 2 1 4 6 5 7여기서 6을 탐색해보자.
3 9 8 2 1 4 6 5 7
-----먼저 배열의 왼쪽 끝 숫자를 확인한다. 6과 비교해서 일치하면 탐색을 종료, 그렇지 않으면 하나 오른쪽에 잇는 숫자를 확인한다.
2
3 9 8 2 1 4 6 5 7
-----일치하지 않았으므로 하나 오른쪽에 잇는 숫자를 확인한다.
3
3 9 8 2 1 4 6 5 7
-----6을 찾을 때까지 비교를 반복한다. 6을 찾았으므로 탐색을 종료한다.
선형 탐색은 선두에서부터 비교를 반복하기에 데이터 수가 많고 대상 데이터가 배열 뒤에 있는 경우, 또는 대상 데이터가 존재하지 않는 경우에는 비교 횟수가 많아져 시간이 걸린다.
참고 서적 :
