[알고리즘] 선형 탐색과 이진 탐색

• 선형 탐색 알고리즘(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를 삽입할 가장 오른쪽 인덱스를 반환

출처 : Python Docs
출처 : 동빈나 Youtube