[파이썬] 순차탐색과 이진탐색

a = [1,2,3,4,5,6,7,8,9,10]

a 리스트에서 내가 8이라는 값의 위치를 찾는 방법은 여러가지이다. 그중에서 순차탐색과 이진탐색을 설명하겠다.

 

순차탐색 (Sequential Search)

순차탐색은 그냥 말그대로 처음부터 이게 8인지 아닌지 확인해가면서 찾는 것이다.

즉 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 만약 찾고자하는 데이터가 제일 끝에 있다면, 데이터 개수가 N일 때 최대 N번의 비교 연산을 수행함으로 최악의 경우 시간 복잡도는 O(N) 이다.

이진탐색 (Binary Search)

이진탐색은 절반씩 쪼개가면서 찾는 것이다. 이때 a list가 정렬되어 있어야만 사용가능하다. 1~10 의 데이터 중 8의 위치를 찾으려면 우선 데이터의 중간값인 5와 8을 비교한다. target 값이 middle 값보다 더 크다. 그러면 다시 start(6)값과 end(10)값을 정의해주고 middle(8) 값과 target 값을 비교한다. 2번만에 target 값을 찾았다. 이진탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

이진 탐색 (재귀문)

이진 탐색(반복문)