[Algorithm] 이진 탐색 정리

이진 탐색(Binary Search)은 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법이다.

언어에 상관없이 이진 탐색은 시작점, 중간점, 끝점을 이용하여 데이터를 탐색한다.

 

리스트에 데이터가 다음과 같이 정렬된 상태로 있다고 가정하자.

0 3 6 9 12 15 18 21 24 27 30

 

시작점인 list[0]의 값은 0일꺼고, 끝점인 list[-1]의 값은 30일 것이다.

그리고 중간 지점은 (시작점 + 끝점 // 2)로 계산하면 5로, list[5]인 15이 될 것이다. ( 소수점은 없앤다. )

 

그리고 찾고자 하는 값이 9라고 가정하자.

먼저 중간 지점인 list[5]의 값인 15과 비교한다. 찾는 값인 9는 중간 지점의 값인 15보다 작다.

그러면 중간점인 list[5]부터 끝점까지는 데이터를 탐색할 필요가 없다.

 

그래서 끝점을 중간점인 list[5]의 왼쪽으로 옮긴다. 새로운 끝점은 list[5]일 것이고,

새로운 중간점은 list[2]인 6이 될 것이다.

 

찾고자 하는 값이 중간점의 값보다 크므로,

이번에는 시작점을 중간점의 오른쪽인 list[2]로 바꿔주고, 끝점은 동일하게 해준다.

중간점은 3이 될 것이다.

 

이제 우리가 찾고자 하는 값인 6이 중간점과 일치한다.

index를 찾았으면 이를 return 하고 탐색을 중단하면 된다.

탐색 과정에서는 시작점이나 끝점과 비교하는 것이 아닌, 매번 중간점과 비교하게 설계하고,

중간점보다 값이 작거나 큼에 따라서 시작점과 끝을 바꿔서 재귀를 돌리는 것이다.

 

이진 탐색의 시간 복잡도는

단계마다 탐색 범위를 절반으로 나누는 것과 동일하니 O(log_2 N)에 비례한다.

순차 탐색인 O(N)에 비해 시간이 절약되는 방법이다.

 

예시 코드는 다음과 같다.

나동빈님의 코드를 참고하였다.

def binarySearch(li, target, start, end):
	if start > end:
    	return None # 찾는 값이 존재하지 않음.
    mid = (start + end) // 2
    if li[mid] == target: # 찾은 경우 중간 점의 리스트를 반환
    	return mid
    
    # 중간점의 값이 찾고자 하는 값보다 큰 경우, 왼쪽을 확인 한다.
    elif li[mid] > target:
    	return binarySearch(li, target, start, mid-1)
    
    # 중간점의 값이 찾고자 하는 값보다 작은 경우, 오른쪽을 확인 한다.
    else:
    	return binarySearch(li, target, mid+1, end)
  
  
result = binarySearch(li, target, 0, len(li))
if result == None:
	print("element isn't exist") 
else:
	print(result + 1)

시작점 > 끝점을 탈출 분기점으로 삼아서, 찾는 데이터가 없을 때 탈출할 수 있게 한다.

 

---

 

그리고 Python에는 bisect이라는 이진 탐색 라이브러리가 존재하고,

이를 이용해서 값이 특정 범위에 속하는 데이터의 개수를 구할 수 있다.

역시 나동빈님의 코드를 참고했다.

 

from bisect import bisect_left, bisect_right

# bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 index 반환
# bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 index 반환

def countByRange(a, leftval, rightval):
    rightidx = bisect_right(a, rightval)
    leftidx = bisect_left(a, leftval)
    return rightidx - leftidx
    
# list
a = [1,2,3,3,3,3,4,4,8,9]

# 값이 4인 데이터 개수 출력
print(countByRange(a, 4, 4)) # result : 2

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(countByRange(a, -1, 3)) # result : 6