Binary Search VS Linear Search

경도현·2021년 6월 21일
1

어떤 자료구조를 언제 선택하는지 중요한 것 처럼 무슨 알고리즘을 언제 선택하는지 배워야 합니다. 왜냐하면 완벽한 자료구조와 알고리즘 조합을 찾아내면, 코드의 속도 자체가 달라지기 때문입니다.
저번에도 말했다시피, 알고리즘은 어떠한 작업을 수행하기 위해서 우리가 따라야하는 절차 및 스텝입니다. ex)음식의 레시피

알고리즘에도 마찬가지로 시간 복잡도(Time Complexity)가 존재합니다. 당연히 적은 절차로 같은 작업을 수행하는 알고리즘이 더 훌륭한 알고리즘입니다.

Binary Search VS Linear Search

둘다 search 알고리즘에 속해 있습니다. 즉, 검색관련에 대한 작업을 수행합니다. 최대한 빠르게 검색 작업을 수행하는 것이죠.

Linear Search

선형 검색은 검색을 하기 위한 가장 "자연스러운" 방법입니다. 만약 10개의 숫자가 있는 배열이 있고, 거기서 7이라는 숫자를 찾는다면 1번 부터 차례로 7이 맞는지 확인할 것입니다. 이런식으로 순서대로 목표값을 찾는 것을 뜻합니다. 처음부터 끝까지 순서대로 차근차근 말이죠.

이러한 선형검색의 경우, 최악의 경우는 찾는 아이템이 맨 마지막에 있거나 혹은 배열에 아예 없는 경우입니다. 이말인즉슨, 배열이 커지면 커질수록 선형검색을 하는 시간 또한 길어지게 된다는 말입니다. 이것을 Linear Time Complexity(선형 시간복잡도) 라고 합니다.
즉, input이 많으면 많을수록 수행하는 시간 역시 선형적으로 증가한다는 소리입니다.

이것보다 발전된 방법이 바로 Binary Search (이진 검색) 입니다.

Binary Search

이진 검색은 모든 배열에 쓸 수 없습니다. Sorted Array(정렬된 배열)에서만 가능합니다.
이처럼 어떤 알고리즘은 특정 자료구조에서만 사용 가능합니다. 선형 탐색은 어느 배열에서도 가능하지만, 이진 탐색은 Sorted Array에서만 가능합니다.

Sorted array

배열들이 순서대로 정렬된 경우를 뜻합니다.

그러나, 이렇게 정렬된 배열에 아이템을 추가하는 것은 정렬이 안된 경우 보다 시간이 더 오래 걸립니다. 왜냐하면 처음부터 일일이 비교하면서 위치를 찾아줘야 하기 때문이죠.
하지만, 정렬된 배열에서 탐색을 하는 것은 정렬이 안된 경우 보다 훨씬 더 빠릅니다.

Binary search에서 Binary(이진)은 0과1을 의미하는 것이 아니라, 반으로 쪼개는 것을 뜻합니다. 하나를 두개로 쪼개는 것이죠.
만약, 1에서 10까지 정렬된 배열이 있고 9를 찾아야 한다고 가정해 봅시다. 선형 탐색과 달리, 이진 탐색에서는 인덱스 0부터 검색하지 않습니다. 중간에서 시작합니다!



따라서 목표의 숫자보다 큰지, 작은지를 보는 것 입니다.
만약, 목표보다 크다면 오른쪽으로 가고, 작다면 왼쪽으로 가게 됩니다. 그리고 해당 프로세스를 반복하게 됩니다. 기준점이 계속 중간으로 이동하는 것이죠.
5 -> 8 -> 9 이런식으로 9라는 아이템은 3번만에 찾을 수 있게 됩니다. 선형 탐색이라면 9번의 시도가 필요한 작업을 말입니다!

이렇게 이진 탐색은 매 스텝마다, 절반의 아이템을 없애기 때문에 매우 빨라집니다. 즉, 자료가 2배가 되어도 작업에 필요한 스텝은 많이 늘어나지 않게 됩니다. 특히 엄청나게 큰 사이즈의 데이터를 처리할 때 효율적이죠.

정리

정리하자면, 이진 탐색은 거대한 배열을 다룰 때 효과적입니다. 그러나 이진 탐색을 하고 싶다면, 배열을 정렬해야 합니다! 그리고 이는 시간이 소요되는 일입니다. 바로 여기서 트레이드 오프가 필요합니다.
검색을 많이 해야 하는 상황이라면, 일단 정렬을 해야한다는 것 입니다. 하지만, 배열을 정렬하려면 아이템 추가시 시간이 소용된다는 것이죠. 이러한 상충관계를 명확히 인지하며 사용해야 합니다.

profile
I'm a Graduate student studying Deep Learning.KR👨‍💻

0개의 댓글