[We-Co] 이진탐색 알고리즘- Python

안녕하세요. 위기의 코딩맨입니다.

오늘은 이진탐색 알고리즘에 대해 알아보도록 하겠습니다.

 

이진탐색 알고리즘은 반복, 순환 구조에 사용되며

알고리즘의 입력으로 정렬한 리스트와 Key 값, 

A의 탐색 범위인 Low와 High가 제공되어야 합니다.

 

 

list_ = [1,3,8,13,13,16,21,26,27,30,33,36,39,41,44,49]를 기준으로 사용하였으며

인자는 리스트, 찾고자하는 숫자, Low, High을 받습니다.

[ 순환 구조 ]

def binary_Search_1(A, Key, Low, High):
  if Low <= High:
    mid_ = (Low+High) // 2
    if Key ==A[mid_]:
      return mid_
    elif Key < A[mid_]:
      return  binary_Search_1(A, Key, Low, mid_-1)
    else:
      return  binary_Search_1(A, Key, mid_+1, High)
  return -1

 

Low와 High으로 항목이 존재하는지 유무를 판단하고

그 크기의 반을 mid로 중간 값을 판단하고

탐색을 성공하면 해당 값의 인덱스를 반환하고

키가 더 작으면 High을 줄여서 순환,

키가 더 크게되면 Low 값을 늘려가면서 값을 찾습니다.

 

찾고자 하는 인덱스가 없으면 -1 값을 반환합니다.

 

[ 반복 구조 ]

해당 알고리즘을 반복구조를 통해서 구현이 가능합니다.

 

def binary_Search_2(A, Key, Low, High):
  while Low <= High:
    mid_ = (Low+High) // 2
    if Key == A[mid_]:
      return mid_
    elif Key < A[mid_]:
      High = mid_ -1
    else:
      Low = mid_ +1
  return -1

 

거의 같은 방식으로 진행되며

Log 값이 High과 같거나 커지면 무한루프는 종료되며, 그렇지 않으면

mid_ 값을 구하고,

순환 구조와 같은 방식으로 값을 구해질 때 까지 무한 루프를 돌게됩니다.

 

 

두 가지의 결과를 확인해보면

binary_Search_1은 33의 숫자의 인덱스를 찾고

binary_Search_2는 13의 숫자의 인덱스를 찾도록 했습니다.

 

binary_Search_1(list_,33,0,len(list_)-1)
binary_Search_2(list_,13,0,len(list_)-1)

 

list_ = [1,3,8,13,13,16,21,26,27,30,33,36,39,41,44,49]의 리스트 기준으로

ㅐ당 인덱스를 잘 반환하는 것을 확인할 수 있습니다.

 

결과

실행 효율성은 순환보다 반복구조가 좋습니다. ㅎㅎ

오늘은 이진탐색 알고리즘에 대해서 간단하게 알아보았습니다.