이진 탐색

이진탐색이란?

이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘으로, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다. 절반씩 데이터를 줄어들도록 만든다는 점은 퀵정렬과 공통점이 있다.

이진탐색 파이썬으로 구현하기

def binary_search1(array, target, start, end):
    if start>end:
        return None;
    mid=(start+end)//2;
    if array[mid]==target:
        return mid;
    elif array[mid]>target: #중간점보다 타겟이 작은 경우
        return binary_search1(array, target, start, mid-1);
    else: #중간점보다 타겟이 큰 경우
        return binary_search1(array, target,mid+1,end);


def binary_search2(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;


n, target=list(map(int, input().split()))
array=list(map(int, input().split()))


result=binary_search2(array,target,0,n-1);
if result==None:
    print('원소가 존재하지 않음.')
else:
    print((result+1),'번째에 존재함.')

단계마다 탐색 범위가 절반으로 줄어드므로 연산 횟수는 logN에 비례. 시간복잡도는 O(logN).

 

파이썬 이진탐색 라이브러리

from bisect import bisect_left,bisect_right
from itertools import count

a=[1,2,4,4,8]
x=4

print(bisect_left(a,x)) #2
print(bisect_right(a,x)) #4


#값이 특정 범위에 속하는 데이터 개수 구하기
def count_by_range(a, left_value, right_value):
    right_index=bisect_right(a,right_value);
    left_index=bisect_left(a,left_value)
    return right_index-left_index;

a=[1,2,3,3,3,3,3,4,4,8,9]
#갑싱 4인 데이터 개수 출력
print(count_by_range(a,4,4)) #2

#값이 1~3 범위에 있는 데이터 개수 출력
print(count_by_range(a,1,3)) #7

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

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

 

파라메트릭 서치(Parametric Search)

파라메트릭 서치란 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
(특정한 조건을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제를 결정 문제로 바꾸어 푸는 것)

일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능.

 

파라메트릭 서치를 이용해서 답을 구할 수 있으려면..

1) 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우

2) 최솟값이 x라면, x 이상의 값에 대해서는 모든 조건을 만족

3) 최댓값이 x라면, x 이하의 값에 대해서는 모든 조건을 만족

 

https://sarah950716.tistory.com/16