알고리즘 : 순차 탐색과 이진 탐색

 

1. Sequential Search Algorithm (순차 탐색)

--->

순차 탐색(Sequential Search)은 데이터를 찾기 위해 리스트의 첫 번째 요소부터 순서대로 확인하는 탐색 알고리즘이다.

1. 알고리즘 동작 원리

1. 리스트의 첫 번째 요소부터 탐색을 시작합니다.
2. 현재 요소가 찾고자 하는 값과 같다면 탐색을 종료합니다.
3. 일치하지 않으면 다음 요소로 이동합니다.
4. 리스트의 끝까지 탐색했음에도 찾고자 하는 값이 없다면, 데이터가 존재하지 않는 것으로 간주합니다.

2. Binary Search (이진 탐색)

--->

이진 탐색은 리스트를 반으로 나누어 탐색을 하는 방식이다.

리스트의 중간 값인 mid와 찾고자 하는 key값을 설정한 후에 mid값을 옮겨가며

key값을 찾는 탐색을 진행한다.

 

이를 의사 코드로 한번 알아보자

이진 탐색

알고리즘으로 나타낸 이진 탐색 코드이다.

빈칸1 : location = mid; 이진 탐색을 하기 위해 mid를 설정했는데 key값인 경우이다.

빈칸2 : low = mid + 1 ,mid값을 오른쪽으로 옮겨주는 절차이다.

 

두 알고리즘을 비교해보면, 이진 탐색은 순차 탐색에 비해서 비교적 빠르게 key값을 찾을 수 있는 장점을 가졌다.

순차탐색은 최악의 경우에는 모든 리스트를 확인해야하는 단점이 존재하기 때문이다.

이를 비교해주는 표를 확인해보자.

속도 및 확인 횟수 차이 표

이는 최악의 경우를 상정했을 때의 탐색 횟수이다.