linear search 선형탐색 vs binary search 이진탐색

이전에 전화번호부 관련 프로젝트를 진행한 경험이 있다.

하지만 전화번호부에 있는 이름들을 다 선형 탐색으로 필터링하고 있었다.

사실 유저가 많지 않기 때문에 선형탐색으로 해도 특별히 문제점을 느끼지 못했다.

 

하지만 유저의 수가 증가할수록 선형 탐색이 아닌 이진 탐색이 필요하다는 것을 느끼게 되었다.

때문에 이 부분은 수정이 필요했다.

 

왜 선형 탐색보다 이진 탐색이 나았는지는 아래 코드 결과를 보면 정확하게 파악할 수 있다.

 

선형 탐색과 이진 탐색을 비교하기 위해 먼저 정렬된 배열을 준비했다.

for문을 돌려 0부터 1000까지의 숫자를 붙여주고 그 배열을 가지고 탐색을 진행했다.

먼저 선형 탐색을 보자.

linear 말 그대로 하나씩 탐색하며 검사하는 방법이다.

30을 찾는다고 가정한다.

for문을 돌면서 array에 있는 하나씩 비교한다.

찾으려는 값 searchValue와 비교해서 값이 존재하면 true를 리턴하며, 

값이 없는 경우 끝까지 루프를 다 돌고 나서 false를 리턴한다.

 

이진 탐색과 비교하기 위해 프린트 문을 찍었다.

당연히 0부터 찾으려는 값까지 출력된다.

30까지 출력한 후 30이 내가 찾으려는 값이랑 같으니 함수는 true를 리턴하며 끝이 난다.

 

그럼 이진 탐색은 어떨까. 

재귀로 작성하는 방법도 있지만 오늘은 while을 사용해서 풀어보려 한다.

가운데 인덱스를 잡아주고 내가 찾으려는 값이 가운데 인덱스의 값보다 같으면, 작으면, 크면으로 나눈다.

 

가운데 인덱스의 값이랑 같다면 바로 true를 리턴하고,

가운데 인덱스의 값보다 작다면 rightIndex는 중간 인덱스의 -1 해준 값으로 변경해준다. (범위를 좁혀나가는 과정)

가운데 인덱스의 값보다 크다면 leftIndex는 중간인덱스의 +1 해준값으로 변경해준다. (이 또한 범위를 좁혀나가는 과정)

 

위 방법을 계속하다 보면 내가 찾으려는 값이 있는지 없는지 확인 가능하다.

while문 안에 얼마나 찍히는지 보면 5번이 찍혔다. 

위 선형 탐색보다 훨씬 작은 수임을 확인할 수 있다.

그래프를 살펴보면 선형 탐색과 이진 탐색은 number of elements가 작으면 별 차이를 느끼지 못한다.

하지만 우측으로 갈수록 두 그래프의 폭이 커짐을 확인할 수 있다.

 

resource : https://www.techtud.com/sites/default/files/public/user_files/tud39880/linearSearch%20vs%20binary%20search%20diagram_0.jpg

이로써 이전 프로젝트는 선형 탐색을 이진 탐색으로 바꾸어 어느 정도 개선이 가능했다.