이분 탐색

Binary Search 이진 탐색

이진 탐색은 중간 값을 비교해 나가면서 탐색 범위를 좁혀가는 방식의 탐색 알고리즘이다

def bin_search(a,key):
  pl = 0
  pr = len(a) -1
  while True:
    pc = (pl+pr)//2     # 비교 값 인덱스
    if a[pc] == key:    
      return pc         
    elif a[pc]<key:     
      pl = pc+1
      # 크면, 중간 +1 값을 pl로 설정
    
    else:
      pr = pc-1
      # 아니면, 중간 -1 값을 pr로 설정

    if pl>pr:
      break
      # pl 이 pr 보다 크다는 것은 바로바로 못 찾겠다는 것이다
      
  return -1

[BOJ] 사냥꾼 8983

→→사냥꾼 문제 링크←←

시작 코드

place.sort()

cnt = 0
for anim in lst:
  e = len(place)-1
  s = 0
  mid = 0
  while s <= e:
    mid = (s+e) // 2
    if place[mid] < anim[0]:
      s = mid +1
    else:
      e = mid-1
  h = abs(anim[0]-place[mid]) + anim[1]
  if h <= L:
    print(mid, s,e)
    cnt += 1
print(cnt)

초반 아이디어

동물 리스트에서 좌표 배열을 하나씩 꺼내서

이분 탐색으로 X 좌표와 place 리스트 원소를 비교해서 찾으면

| x - a | + b 계산 후 counting

결론

사람들에게 물어물어 알아본 결과
[참고 link] https://velog.io/@me4n/PYTHON-%EB%B0%B1%EC%A4%80-8983

cnt = 0
for anim in lst:
  e = M-1
  s = 0
  
  while s <= e:
    mid = (s+e) // 2
    h = abs(anim[0]-place[mid]) + anim[1]
  
    if h <= L:
        cnt += 1
        break
    elif place[mid] < anim[0]:
      s = mid +1
    else:
      e = mid-1
  
  
print(cnt)

계산값을 반복문 안에서 찾으면 빨리 찾을 수 있었던 것이었다