[Algorithm] 01. 선형탐색 알고리즘 VS 이진 탐색 알고리즘

00. 탐색이 뭔가요?

 탐색은 저장된 정보들 중에서 원하는 값을 찾는 것이다.

 

 

01. 선형 탐색 알고리즘(linear search algorithm)

 처음부터 하나씩 찾아가는 방법

 

 

02. 이진 탐색 알고리즘(binary search algorithm)

 간단히 말하면 이진탐색 알고리즘은 반띵해서 확인하기이다. 이진탐색 알고리즘의 원리는 리스트의 중앙값을 계속 확인한다. 정렬이 되어있기에 우리가 찾는 어떤 특정값과 리스트의 중앙값을 비교한다면 찾아갈 수 있있다. 만약 중앙값보다 작으면 왼쪽의 리스트만 확인하면 되고 중앙값보다 크면 오른쪽의 리스트만 확인하면 된다. 만약 찾는 값이 중앙값보다 작을 경우, 왼쪽의 리스트를 확인해야하는데 이 때 왼쪽의 리스트에서 다시 중앙값을 확인한다. 이 때 중앙값은 리스트 전체에서 1/4 지점이라고 볼 수 있으니 다시 중앙값과 크기를 비교하고 왼쪽영역인지 오른쪽 영역인지 확인할 부분을 정한다. 이렇게 찾아가다가 값이 나오지 않을 경우 없는 것이고 있다면 출력하면 된다.

 

 

 

03. 어떤 것이 더 좋나요?

이진탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 한다. 정렬된 리스트가 아니면 알고리즘은 적용이 불가능하며, 이진탐색 알고리즘은 가장 금방되는 경우 1번 가장오래 걸리는 경우 4번 총 길이 16개를 탐색한다고 가정했을때 아래와 같은 결과가 나올 수 있다.

리스트의 길이	이진탐색
16	4
32	5
64	6
128	7