선형 탐색

배열에서 데이터를 탐색하는 알고리즘

데이터가 마구잡이로 나열돼 있어도 적용할 수 있다
작업은 단순하게 배열의 앞에서 부터 순서대로 데이터를 확인한다.

1. 왼쪽에서부터 숫자를 확인한다.
2. 값을 비교하며 찾으려는 값과 일치하면 탐색을 종료한다.

선형 탐색은 선두에서부터 순서대로 비교를 반복한다.
이 때문에 데이터 수가 많고 대상 데이터가 배열 뒤에 있는 경우,
또는 대상 데이터가 존재하지 않으면 비교횟수가 많아져 시간이 걸린다.

계산시간 = O(n)

이진 탐색

배열에서 데이터를 탐색하는 알고리즘

선형 탐색과 달리, 데이터가 정렬된 경우에만 적용할 수 있다.
배열의 가운데 있는 데이터와 대상 데이터를 비교해서 대상 데이터가 정중앙보다 오른쪽에 있는지 왼쪽에 있는지 알 수 있다.
한 번의 비교만으로 탐색해야할 범위를 반으로 줄일 수 있다.
이것을 대상 데이터를 찾거나 존재하지 않는다는 것을 알 때까지 반복한다.

1. 배열에서 중간값을 찾아 찾으려는 값과 비교한다.
   • 찾으려는 값이 중간값 기준으로 왼쪽에 있는지 오른쪽에 있는지
2. 찾으려는 값보다 작은 값들은 후보에서 제외하고 남은 배열의 중간값을 찾는다.
3. 다시 찾으려는 값과 비교하여 필요가 없어진 값들은 후보에서 제외한다.
4. 대상 데이터를 찾거나 존재하지 않는다는 것을 알 때까지 반복한다.

이진 탐색은 배열이 정렬돼 있다는 것을 활용해서 탐색할 범위를 매번 반씩 줄일 수 있다. 탐색할 범위가 한 개의 데이터가 되면 탐색이 종료된다.

배열의 정중앙에 있는 수와 비교해서 탐색 범위를 반으로 줄이는 작업을 log$_2$n회 반복하면 데이터를 찾을 수 있다.

계산시간 = O(log n)

이진 탐색의 계산 시간이 선형 탐색에 비해 지수적으로 빠르다.
단, 이진 탐색을 하려면 항상 데이터가 정렬돼 있어야 하는데, 데이터를 추가할 때는 정확한 위치에 추가해야 하는 등 배열을 관리하기 위한 시간이 든다.
반면 선형 탐색에서는 배열 안의 데이터가 아무렇게 나열되어 있어도 괜찮기 때문에 데이터 추가를 신경 쓰지 않고 단순히 마지막에 추가하면 되므로 시간이 걸리지 않는다.

어떤 탐색을 사용할지는 검색과 추가 중 어떤 작업을 빈번하게 하는지 고려해서 결정하는 것이 좋다.

Reference

• 『알고리즘 도감』, 이시다 모리테루, 미야자키 쇼이치 - 제이펍
• 『알고리즘 도감』 어플