[코딩테스트 준비] 이분탐색과 파라메트릭 서치

이분탐색: left, right로 중간값을 찾아가면서 탐색한다

def bin_search(li,n):
  l=0
  r=len(li)-1
  while l<=r:
    mid=(l+r)//2
    print(mid)
    if li[mid]==n:
      return mid
    if li[mid]<n:
      l=mid+1
    else:
      r=mid-1
  print("theres no ")
  return mid #no such value.

파라메트릭 서치: 끝값을 보고 움직이거나 그 중간을 가거나...

def para_search(li,n): #n 이하인 수 중 가장 오른쪽 값
  cur=-1
  step=len(li)
  while step>0:
    if li[cur+step]>n:
      step//=2
    else:
      cur=cur+step
  return cur

 

 

블로그 챌린지 중이라 급하게 씁니다..^^