[이론] 이진탐색 / 파라메트릭서치

이진탐색

- 반으로 쪼개면서 탐색하기

: 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정

- 시간복잡도 O(logn)

- 처리해야할 데이터의 개수나 값이 1000만 이상이면 이진탐색 떠올리자 

- 구현

#10개의 수입력했을 때, 7이 몇번째 있는지 찾기 
10 7
1 3 5 7 9 11 13 15 17 19

 1) 재귀함수

#재귀함수로 구현한 이진 탐색 소스코드
#
import sys
sys.stdin = open("input.txt","r")

def binary_search(arr,target,start,end):
    if start>end:
        return None
    mid=(start+end)//2
    #목표값을 찾은 경우
    if arr[mid] == target:
        return mid
    #목표값이 중간값보다 작은 경우
    elif arr[mid]>target:
        return binary_search(arr,target,start,mid-1)
    #목표값이 중간값보다 큰 경우
    elif arr[mid]<target:
        return binary_search(arr,target,mid+1,end)

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

result=binary_search(arr,target,0,n-1)
if result==None:
    print("원소가 존재하지 않음")
else:
    print("원소가 %d번째 존재함" %(result+1))

 

 2) 반복문 

#반복문으로 구현한 이진탐색
#
import sys
sys.stdin = open("input.txt","r")
def binary_search(arr,target,start,end):
    while start<=end:
        mid=(start+end)//2
        #목표값을 찾은경우
        if arr[mid]==target:
            return mid
        #목표값이 중간값보다 작은 경우
        elif arr[mid]>target:
            end=mid-1
        #목표값이 중간값보다 큰 경우
        else:
            start=mid+1
    return None

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

result=binary_search(arr,target,0,n-1)
if result==None:
    print("원소가 존재하지 않음")
else:
    print("원소가 %d번째 존재함" %(result+1))

 

파라메트릭 서치(parametric search)

: 최적화문제를 결정문제(예 혹은 아니오로 답하는문제)로 해결하는 기법

- 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제

- 범위내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제이면, 이진탐색으로 결정문제를 해결하면서 범위를 좁혀간다 

 

 

 

 

 

연관포스트 : hiruby.tistory.com/7