- 선형 탐색 알고리즘(Linear Search Algorithm)
가장 원시적인 형태의 데이터 탐색 알고리즘
리스트에서 찾으려고 하는 값을 맨 앞부터 끝까지 차례대로 탐색해 찾는 것
검색할 리스트의 길이가 길면 길수록 비효율적이지만 구현 코드 자체는 단순하여 구현이 쉽고 리스트가 정렬이 되어 있지 않은 상태여도 사용할 수 있다는 장점이 있다.
선형 탐색은 데이터를 찾기 위해서 데이터를 하나씩 전부 확인하므로 시간 복잡도는 최악의 경우 O(n)
이 성립한다.
- 이진 탐색 알고리즘(Binary Search Algorithm)
오름차순으로 정렬된 리스트에 대해서 특정 값의 위치를 찾는 알고리즘
시작점과 도착점을 설정한 후 중간점을 구해서 해당 중간값과 해당 값을 비교하여 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용
이진 탐색은 데이터를 계속해서 반으로 분할하며 탐색하기 때문에 시간 복잡도는 최악의 경우
O(log n)
이 성립한다.
반드시 정렬 기준이 있어야하며 정렬되어 있어야 한다는 선결 조건이 있지만 정렬된 데이터에서 최고의 효율을 보여주는 탐색이다.
- 위의 탐색 과정은 선형 탐색의 과정과 이진 탐색의 과정을 시각적으로 표현한 그림이다.
- 선형 탐색 알고리즘은 처음부터 하나하나씩 탐색을 진행하면서 찾는 값에 도달하게 되는 순간 종료를 하게 된다. 반면 이진 탐색 알고리즘은 중간값을 찾은 뒤 중간값을 기준으로 좌우를 확인하여 범위에 부합하는 부분만 남기고 범위에 부합하지 않는 부분은 탐색을 진행하지 않는다.
- 위의 그림은 이진 탐색을 수행할 때 최악의 경우 탐색하는 횟수를 나타내는 것이다.
- 위의 그림은 이진 탐색을 수행할 때 최선의 경우 탐색하는 횟수를 나타내는 것이다.
- 아래 python 코드는 이진 탐색을 수행하는 코드다.
def binary_search(array, target, start, end):
while start <= end:
# 중간값 mid
mid = (start + end) // 2
# 우리가 찾고자하는 값과 일치한다면?
if array[mid] == target:
return mid
# 중간값을 기준으로 우리가 찾고자하는 값이 왼쪽에 있다면?
# 중간값 기준 오른쪽 범위는 탐색할 필요가 없음
# 따라서 도착점을 mid - 1로 변경
elif array[mid] > target:
end = mid - 1
# 중간값을 기준으로 우리가 찾고자하는 값이 오른쪽에 있다면?
# 중간값 기준 왼쪽 범위는 탐색할 필요가 없음
# 따라서 시작점을 mid + 1로 변경
else:
start = mid + 1
- 위와 같은 방식으로 이진 탐색을 수행하는 함수를 작성하여 탐색할 수 있다. 하지만 python의 가장 큰 장점은
다수의 효율적인 라이브러리
가 존재한다는 것이다. 그래서 이진 탐색과 관련된 라이브러리를 이용해보려한다.- 이진 탐색과 동일한 라이브러리인
bisect
라이브러리가 존재한다.- 아래 python 코드는
bisect
라이브러리의 사용법에 대한 코드다.
# 예시1
from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_range(array, left_value, right_value):
right_index = bisect_right(array, right_value)
left_index = bisect_left(array, left_value)
return right_index - left_index
# 배열 선언
array = [1, 2, 3, 3, 3, 4, 4, 8, 9]
# 값이 4인 데이터의 개수를 출력
print(count_range(array, 4, 4))
# 값이 [-1, 3] 범위 사이에 있는 데이터의 개수를 출력
print(count_range(array, -1, 3))
# 예시2
from bisect import bisect_left, bisect_right
array = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(array, x)) # 2
print(bisect_right(array, x)) # 4
- bisect_left(array, x) : 배열이 정렬된 상태를 유지해야하면서 배열 array에 x를 삽입할 가장 왼쪽 인덱스를 반환
- bisect_right(array, x) : 배열이 정렬된 상태를 유지해야하면서 배열 array에 x를 삽입할 가장 오른쪽 인덱스를 반환
이렇게 유용한 정보를 공유해주셔서 감사합니다.