이진 탐색 (Binary Search) (0) - 순차 탐색 (Sequential Search)

이진 탐색 알고리즘을 들어가기 전에 먼저 순차 탐색 (Sequential Search) 에 대해서 알아보자.

순차 탐색이란 말 그대로 리스트 내에서 특정 데이터를 찾고 싶을 때, 앞에서부터 순차적으로 데이터를 비교해서 탐색하는 알고리즘이다. 즉, 리스트내의 모든 데이터에 접근하며 차례대로 확인하게 된다. 따라서 시간이 여유롭다면 데이터의 개수가 아무리 많더라도 반드시 원하는 데이터를 찾아낼 수 있다는 장점이 있다. 

순차 탐색 알고리즘이 수행되는 곳은 정말 다양하다. 아래의 경우에도 순차 탐색이 사용된다.

• 리스트에 특정 값의 원소가 있는지 체크할 때
• 리스트에서 특정 값을 가지는 원소의 개수를 구할 때 ( count() 메서드 )

순차 탐색 알고리즘의 소스코드는 아래와 같다.

---

순차 탐색의 시간 복잡도는 다음과 같다. 순차 탐색은 정렬 여부에 관계없이 모든 데이터에 차례대로 접근한다. 따라서 데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하게 되므로 시간 복잡도는 최악의 경우, O(N)이 된다.