이진탐색

이진탐색

정의: 오름차순으로 정렬된 리스트에서 범위를 반씩 줄여가며 특정한 값의 위치를 찾는 알고리즘이다.

구현

1.두 개의 start,end포인터를 초기화시킨다.
2.중앙값과 목표값을 비교한다.

• 중앙값이 목표값보다 작다면 start를 중앙값의 오른쪽으로 옮긴다.
• 중앙값이 목표값보다 크다면 end를 중앙값의 왼쪽으로 옮긴다.
• 중앙값이 목표값과 같다면 종료한다.
  3.start가 end를 넘어섰다면 목표값을 찾지 못했기에 종료한다.

코드

def binary_search(arr,target):
    start,end=0,len(arr)
    
	#start가 end보다 전일 경우에만 탐색
    while start<=end:
    	#중앙값의 인덱스 계산
        mid=(start+end)//2
    	#목표값과 중앙값을 비교하며 범위를 반씩 줄인다.
        if arr[mid]<target:
            start=mid+1
        elif arr[mid]>target:
            end=mid-1
        else:
            return mid
    #특정값을 찾지 못했으므로 쓰레기값 반환
    return -1

nums = [2,4,6,8,10,12]

print("binary_search",binary_search(nums,target=4))
print("binary_search",binary_search(nums,target=5))

$ python test.py
binary_search 1
binary_search -1

start와 end를 중앙값과 목표값을 비교하며 범위를 반씩 줄여나가기 때문에 일반적인 탐색보다 logN이라는 빠른 시간복잡도를 가지고 있다.하지만 주의할 점은 반드시 탐색하는 배열은 정렬된 상태 이어야한다는 것이다.

이진탐색을 통한 범위탐색

관련문제:프로그래머스 순위검색

상황:배열의 크기가 n인 배열에서 특정값 이상인 요소들의 수를 구하여라

1. 완전탐색
   ->배열의 모든요소를 돌아보며 특정값 이상인 수를 센다.(시간복잡도:n)

2. 이진탐색
   ->배열을 정렬 후 특정값의 인덱스를 찾고 전체 길이에서 뺀다.(시간복잡도:nlogn(배열을 정렬하는 시간)+logn(특정값을 탐색하는 시간))

위의 상황을 봤을 때는 당연히 완전탐색으로 구현하는 것이 시간복잡도면에서 빠르고 간단해서 좋다.하지만 특정값 이상인 요소의 수를 구하는 명령이 k번 수행되었다고 한다면
1번은 시간복잡도가 nk
2번은 시간복잡도가 nlogn(처음 한번만 정렬하기 때문에 고정)+klogn(이진탐색을 k번 수행)
위처럼 될 것이다.따라서 (n>k and k<logn) 또는 (n<k)인 상황에서 2번이 유리하게 작용한다.특히 관련문제의 상황은 n<k이므로 2번을 사용해야 한다.

종류

1. binary_left(특정값 이상인 수중 가장 왼쪽 인덱스 찾기)

ex) [2,4,6,8,10,12]에서 특정값이 5라면 특정값 이상인 수는 [6,8,10,12]이므로 6의 인덱스 반환

구현

def binary_left(arr,target):
	#start,end를 초기화
    start,end=0,len(arr)
    while start<=end:
        mid=(start+end)//2
        #start는 항상 target 이상인 수의 인덱스를 보장
        if arr[mid]<target:
            start=mid+1
        #end는 항상 target 미만의 수의 인덱스를 보장
        else:
            end=mid-1
    return start
nums = [2,4,6,8,10,12]

print("binary_left",binary_left(nums,target=5))

binary_left 2

2. binary_right(특정값 초과의 수중 가장 왼쪽 인덱스 찾기)

ex) [2,4,6,8,10,12]에서 특정값이 6라면 특정값 이상인 수는 [8,10,12]이므로 8의 인덱스 반환

구현

def binary_right(arr,target):
	#start,end를 초기화
    start,end=0,len(arr)
    while start<=end:
        mid=(start+end)//2
        #start는 항상 target 초과인 수의 인덱스를 보장
        if arr[mid]<=target:
            start=mid+1
        #end는 항상 target 이하인 수의 인덱스를 보장
        else:
            end=mid-1
    return start
    
nums = [2,4,6,8,10,12]

print("binary_right",binary_left(nums,target=6))

binary_right 3

공통로직

두 개의 포인터(start,end)를 설정하므로 모든 탐색이 끝났을 경우 반환을 할 포인터를 정해야한다.binary_left,binary_right의 경우 반환할 포인터가 start이므로 start를 중심으로 로직을 생각해야한다.

#binary_left
if arr[mid]<target:
	start=mid+1
#binary_right
if arr[mid]<=target:
    start=mid+1

binary_left의 경우
"중앙값이 목표값 미만이라면 start의 중앙값의 인덱스보다 오른쪽으로 설정"->"start에는 절대 목표값 미만인 수의 인덱스를 두지 않겠다"->"모든 탐색이 끝난다면 start는 목표값 이상인 수의 인덱스를 보장한다."
binary_right인 경우
"중앙값이 목표값 이하라면 중앙값의 인덱스보다 오른쪽으로 설정"->"start에는 절대 목표값 이하인 수의 인덱스를 두지 않겠다"->"모든 탐색이 끝난다면 start는 목표과 초과인 수의 인덱스를 보장한다."
라는 해석이 가능하다.

관련패키지

from bisect import bisect_left, bisect_right

print("bisect_left",bisect_left(nums,5))
print("bisect_right",bisect_right(nums,6))

bisect_left 2
bisect_right 3