[자료구조] 순차탐색과 이진탐색

순차 탐색(Sequential search)

• 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색 O(N)의 시간복잡도를 가짐
• 검색할 리스트의 길이가 길면 비효율적
• 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있음

 

이진탐색(Binary search)

• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
• O(logN)의 시간 복잡도를 가짐
• 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됨
• 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있음
• 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수