[파이썬 알고리즘] 이진 탐색(Binary Search)

백준 문제를 풀다보니 골드 문제에서 보이기 시작한 이진 탐색 문제를 좀더 잘 알고있어야 할듯 싶어 알고리즘을 작성하였다.

 

이진탐색 (바이너리 서치)

Big O 는 O(log n)

정렬된 자료를 반으로 나누어 탐색하는 방법

주의점: 자료는 오름차순으로 정렬되어있어야함.

이진트리, 바이너리서치는 코딩 인터뷰 단골 문제라고 한다.

 

구현을 위한 준비

target : 찾고자 하는 값

data : 오름차순으로 정렬된 list

start : data의 첫 인덱스

end : data의 마지막 인덱스

mid : start,end의 중간 인덱스

 

구현 개요

자료의 중간 값이 mid를 찾고자 하는 값인기 검사

아니라면 대소관계를 비교하여 start,end 값을 이동함.

동인 연산을 반복함.

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

# 테스트용 코드
if __name__ == "__main__":
  li = [i**2 for i in range(11)]
  target = 9
  idx = binary_search(target, li)

  if idx:
      print(li[idx])
  else:
      print("찾으시는 타겟 {}가 없습니다".format(target))

(문제를 풀다가 알게되면 문제 추가할 예정)

백준 1629 : https://www.acmicpc.net/problem/2110