이분탐색 (이진탐색)_백준 사냥꾼

www.penjee.com ,https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search 참조

이진 검색 : 오름 차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘.

 

n개의 원소가 오름차순으로 정렬된 배열 A 에서 이진 검색을 하는 과정의 경우

 

검색 범위의 맨앞 맨 끝 중앙의 인덱스를 각각

pl, pr, pc 라고 하면

 

검색을 시작할 때 

 

pl = 0

pr = n-1

pc = (pl+pr)//2

 

로 초기화 한다.

 

이때 내가 찾아야 할 값 key값(위의 그래픽에서 37)보다 pc가 작다면  배열이 오름차순 되어있어 pc이하의 값은 다시 볼 필요가 없으므로 pl = pc+1 값으로 바꿔준다. 

 

이렇게  내가 찾고자 하는 key값과 pc값을 비교하며 같으면 검색에 성공으로 끝낸다.

 

이진 검색의 종료 조건

• A [pc]와 key가 일치하는 경우
• 검색 범위가 더 이상 없는 경우 (pl> pr)

시간 복잡도

반복할 때마다 검색 범위가 절반으로 줄어들기 때문에 검색하는데 필요한 비교 횟수는 평균 log n

검색에 실패할 경우( log(n+1)]번 , 검색에 성공한 경우 (log(n-1))

 

백준 사냥꾼 문제

import sys
input = sys.stdin.readline

m, n, L = map(int,input().split())          #사대갯수, 동물수, 사격거리 입력

sr = list(map(int,input().split()))
sr.sort()

animal = [list(map(int,input().split() ))for _ in range(n)]

count = 0
for a,b in animal:
    pl = 0
    pr = len(sr)-1 #인덱스
   
    while pl<pr:  #동물의 위치는 항상 사대의 범위 안에 있음, 따라서 사대안에서 동물의 위치 와 가장 가까이 있는 사대를 이분탐색으로 찾는다
        pc = (pl+pr)//2
        if a>sr[pc]:   #사대의 위치가 동물의 위치보다 작아?
            pl = pc+1  
        else:  #동물의 위치가 사대와 일치하거나 큰경우다. 따라서 같은경우가 있으므로 pr = pc
            pr = pc # 왜? -1을 하면 5가 나온다
    #while  을 같지 않은 경우 나왔다면? pr은 pc 혹 은 사로의 끝 사로의 끝으로 나온경우는 동물이 끝사로에 가깝다는 뜻

    
    if (abs(sr[pr]-a))+b <= L or (abs(sr[pr-1]-a))+b <= L: #따라서 사로의 끝으로 검사하거나 끝에서 가장 가까운 사로를 검사
            count +=1

print(count)

• 이분 탐색을 활용하기에 앞서 어떤 값을 찾아야 하는지 고민한다.
• 사냥감이 사대의 사정거리 안에 들어온다면  사냥이 가능하므로 사냥감을 key 값으로 사대를 이분탐색 진행한다
  여기서 사대의 위치와 사냥감의 위치는 완벽하지 않을 수 있다. 하지만 사격 사정거리와 사대와 사냥감의 거리를 구하는 공식을 문제에서 알려주었기 때문에
  
  사냥감과 가장 가까운 사대의 위치를 찾아 이분탐색을 한 후 사정거리 안에 들어오는지를 확인하여 들어온다면 
  count +=1을 해준다.