선형 탐색 / 이진 탐색

언젠가 칠지도 모르는 코딩테스트 준비 및 개발자라면 알고리즘은 필수로 알아야하기에 배운 것들을 정리하려합니다.

틀린 내용 및 부족한 내용이 있을 수 있다면 댓글 달아주시면 수정 및 추가하도록 하겠습니다!

 

 

우선 오늘은 탐색방식 중에 2가지(선형 탐색/이진 탐색)를 확인해 보겠습니다

선형 탐색(Linear Search) : 리스트의 처음부터 끝까지 하나씩 탐색을 진행하는 것입니다. 아래 예시를 먼저 보시죠!

리스트 내에서 8을 찾을때 위와같이 4회만에 8을 찾은 것이 확인이 됩니다.

 

이진 탐색(Binary Search) : 이진 탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 합니다. 정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능합니다. 여기서 이진의 의미는 한번 적용할때마다 탐색범위가 절반이 되기 때문입니다!

위에 보시면 단 2번 만에 8을 찾은 것을 확인할 수 있습니다!

 

하지만 이진 탐색의 단점은 리스트가 정렬이 되어있어야 합니다 ㅠㅠ

그럼 다음 시간에는 정렬방식에 대해 알아보겠습니다!