[알각코] 인프런 4-1 이분검색

이분검색

문제 정보는 인프런의 파이썬 알고리즘 문제풀이 코딩테스트에 있습니다!

문제풀이

import sys
sys.stdin = open("input.txt", "r")
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
lt = 0
rt = n-1

while lt <= rt:
  mid=(lt+rt)//2
  if a[mid] == m:
    print(mid+1)
    break
  elif a[mid] > m:
    rt=mid-1
  else:
    lt=mid+1

sorting해서 첫 번째와 마지막을 계산해서 해당 범위 내에 2등분해서 접근하는 방식 m이 중간값이 a[mid]인데 이와 같으면 이 아이를 추출, m보다 크면 마지막 값을 가리키고있는 rt가 mid-1 번째로 범위를 좁히고, m보다 작으면 첫번쨰를 가리키고 있는 lt를 mid+1로 옮겨 범위를 좁혀 다시 반복한다.