2021.2.25 TIL : [자료구조] 순차 탐색과 이진 탐색(Sequential Search and Binary Search)

순차 탐색(Sequential Search)이란 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법이다. 

데이터 정렬 유무에 상관 없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점에서 O(N)의 시간 복잡도를 가진다. 

순차 탐색 코드는 여기에서 확인할 수 있다. 

 

이진탐색(Binary Search)은 배열 내부 데이터가 이미 정렬 되어 있는 상황에서만 사용 가능한 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.

이진 탐색은 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 탐색 시간에서 O(log N)의 시간 복잡도를 가진다. 여기에서 이진 탐색 코드를 확인할 수 있다.