[Algorithm] 이진 탐색 | Binary Search

 

1. 순차 탐색

 

: 가장 기본적인 탐색 방법

 

- 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인

- 정렬되지 않은 리스트에서 데이터를 찾을 때 사용

- 파이썬의 count() 메서드 내부에서 순차 탐색이 사용된다.

 

📌 시간 복잡도: O(n)

 

# target = 찾고자하는 원소
def search(n, target, array):
	for i in range(n):
    	# 현재의 원소가 target과 동일하면
    	if array[i] == target:
        		return i # 현재의 위치 인덱스 반환

 

 

2. 이진 탐색(이분 탐색)

 

: 범위를 절반씩 나누며 탐색하는 방법

 

- 배열 내부 데이터가 정렬되어 있어야 사용이 가능

- 변수 3개 필요: 시작점, 끝점, 중간점

- 중간점이 실수 일 때는 소수점 이하를 버린다.

- 찾으려는 데이터와 중간점 위치의 데이터를 비교하며 탐색

📌 시간 복잡도: O(logN) 보장

 

def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start+end) //2
        
        if array[mid] == target:
        	return mid
        
        elif array[mid] > target:
        	end = mid -1
            
        else:
        	start = mid + 1
            
    return None

 

📌 파이썬 내부 라이브러리 bisect

 

- bisect_left(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환

- bisect_right(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

 

from bisect import bisect_left,bisect_right

a = [1,3,4,5,5,6,6]
x = 4

print(bisect_left(a,x)) # 3
print(bisect_right(a,x)) # 5