Search Algorithm-탐색 알고리즘

탐색 알고리즘

탐색 알고리즘으로 데이터 세트에서 데이터를 검색하는데, 여기서 데이터 세트는 데이터의 모음을 말합니다.

 

대표적인 탐색 알고리즘으로 두 가지 알고리즘이 있습니다.

• 선형 탐색
• 이진 탐색

선형 탐색

선형 탐색은 데이터 세트에 들어있는 모든 데이터를 하나하나 비교하면서 원하는 데이터를 찾는 탐색 방식입니다. 처음부터 끝까지 모든 요소를 검사하는 알고리즘이므로 순차 탐색이라고 부르기도 합니다. 

 

먼저 선형탐색의 예시를 한 번 들어보겠습니다. 

a_list 라는 리스트가 있고 91이 리스트에 있는지 없는지 확인하는 linear_search 라는 함수를 만들어내야합니다. 

위의 linear_search함수를 보자면 먼저 인자로 리스트와 n이라는 변수에 하나의 값을 받습니다.  그리고 포문을 이용해서 그 리스트에 있는 값들을 n과 비교해 같으면 True 값을 리턴합니다. 만약 리스트에 n과 같은 값이 없다면, 포문이 종료되고 False값을 리턴합니다.

📌else문을 이렇게 포문안에 넣는 실수를 할 수도 있는데, 이렇게 되면 a_list의 첫번째 값이 n과 같지 않으면 바로 포문, 함수가 종료되고 False값이 리턴됩니다.

 

시간 복잡도

👉선형 탐색의 시간 복잡도는 0(n)입니다. 즉 선형 탐색 알고리즘의 최선의 경우는 0(1), 최악의 경우에는 10개의 요소가 있는 리스트에서 0(10)의 시간 복잡도를 가질 것 입니다. 

 

이진 탐색

이진 탐색은 탐색하고자 하는 리스트를 1/2로 줄여나가는 탐색 방식으로서, 데이터가 정렬된 상태일 때 사용할 수 있는 탐색 알고리즘 입니다.

위의 binary_search함수를 보자면 먼저 인자로 a_list와 n이라는 인자에 하나의 숫자를 받습니다. first라는 변수에 a_list의 첫번째 인덱스를 의미하는 0, last에는 a_list의 마지막 인덱스인 len(a_list)-1을 담아줍니다. 여기서 -1을 하는 이유는 리스트는 0부터 시작하기 때문입니다. mid 라는 변수에 (first + last)//2를 해주어 배열된 리스트의 중간값을 구합니다. 만약 n의 값이 a_list[mid]의 숫자보다 크다면 first = mid +1을 하여 a_list[mid]의 값보다 큰 값들만 n과 비교합니다. 반대로 n의 값이 a_list[mid]의 숫자보다 작다면 last = mid -1을 해주어 a_list[mid] 보다 작은 값들만 n 과 비교하고 이를 반복합니다.  만약 a_list[mid]의 값과 n의 값이 같다면 True를 리턴하고, 그렇지 않다면 False를 리턴합니다.

 

시간 복잡도

👉이진 탐색 알고리즘의 시간 복잡도는 0(log₂ n) 입니다. 즉, 데이터가 많으면 많을수록 선형 탐색보다 효율적입니다. 

 

선형 탐색	이진 탐색
데이터 정렬❌	데이터 정렬⭕
시간 복잡도: 0(n)	시간 복잡도: 0(log2 n)

 

따라서 데이터가 정렬되어 있지 않다면 선형 탐색, 정렬되어 있다면 더 효율적인 이진 탐색을 사용하면 더 효율적으로 탐색을 할 수 있습니다.