이진 검색(Binary Search) vs 선형 검색(Linear Search)

오늘은 배열에서의 2가지 검색(Search) 알고리즘을 비교해보는 영상을 보고 작성하였다.

 

알고리즘은 어떠한 작업을 수행하기 위해 우리가 따라야하는 절차, 스텝들이다.

 

이번에 다루는 알고리즘과 다른 알고리즘 그룹으로는 정렬(Sorting) 알고리즘이 있다.

 

선형 알고리즘(Linear Search Algorithm)

이 알고리즘은 검색을 하기위한 가장 단순한 단계일 수 있다.

 

이 때, 최악의 시나리오가 두 가지 있다.

 

먼저, 찾는 아이템이 배열의 끝에 존재할 때이다. 이 상황에는 배열의 길이만큼 수행해야할 스텝이 길어진다.

 

또 다른 하나는 배열에 찾는 아이템이 없는 경우이다.

 

그리고 위와 같은 경우들을 선형 시간복잡도(Linear Time Complexity)라고 한다.

 

Input이 커지면 소요되는 시간이 선형적으로 증가한다.

y = x

의 1차함수 그래프처럼 말이다.

 

이진 검색 알고리즘(Binary Search Algorithm)

먼저! 이진 검색 알고리즘은 모든 배열에는 사용이 불가능하다.

 

이 알고리즘은 정렬된 배열(Sorted Array)에서만 사용 가능하다.

 

이처럼 어떤 알고리즘은 특정 자료구조에서만 사용이 가능하다.

 

정렬된 배열은 오름차순이나 내림차순으로 정렬된 배열을 말하고,

여기에 아이템을 추가하는 것은 정렬이 안 된 경우보다 시간이 더 소요된다.

 

그러나, 정렬된 배열에서 검색을 하는 것은 정렬이 안 된 경우보다 훨씬 빠르다.

 

정렬이 안 된 배열에 아이템을 추가하는 경우, 배열 마지막 공간에 원하는 아이템을 추가하면 끝이다.

 

하지만, 정렬된 배열의 중간 값에 해당하는 아이템을 추가하려는 경우,

추가할 아이템보다 오른쪽에 있어야 할 아이템을 찾고 그 왼쪽에 추가해야 한다.

 

그리고 이 작업을 Index#0부터 시작해 각각 비교해야 한다.

 

이 작업을 통해 배열의 추가, 정렬에 시간을 투자했다면 검색 시 보람을 느낄 수 있다.

 

여기서, 이진 검색의 '이진'의 뜻은 0과 1을 의미하지 않는다.

 

반으로 나누는 것을 의미한다.

 

선형 검색과 달리 이진 검색은 Index#0부터 검색하지 않는다.

 

배열의 중앙에서 검색을 시작한다.

 

주어진 배열이 오름차순으로 정렬된 정수형 배열일 때,

 

1. 배열 가운데의 아이템이 목표보다 큰 지 작은 지 판단한다.

 

가운데의 숫자가 목표보다 크면 두 개로 나눈 배열의 왼쪽에서 검색을 시작한다.

 

반대라면 배열의 오른쪽에서 검색을 시작한다.

 

2. 두 개로 나눈 배열 중 하나에서 검색을 시작하여 또 1번의 과정을 반복한다.

 

위와 같은 과정을 통해 배열에서 아이템을 찾게 된다.

 

배열의 크기가 2배가 되더라도 아이템을 찾을 때 필요한 스텝 수는 똑같이 2배 증가하지 않는다.

 

이진 검색은 매 스텝마다 절반의 아이템을 제외시키기 때문이다.

 

극단적인 예로 10000개의 아이템이 있는 배열에서 선형 검색은 최악의 경우 10000번의 검색을 필요로 하지만,

이진 검색은 최악의 경우에도 14번의 검색만으로도 목표 아이템을 찾을 수 있다.