[이진탐색] Binary Search - Python

이진탐색 Binary Search

Binary Search

이진탐색과정

• 이진 탐색의 경우 정렬된 상태에서 수행해야합니다.
• 이진탐색의 경우 크기가 절반씩 줄어듦으로 순차탐색보다 빠릅니다.

 

1. 중간 위치를 찾은 뒤 찾는 값과 비교합니다.
2. 같으면 해당 위치를 return합니다.
3. 찾는 값이 중간 위치보다 작으면 왼쪽에서 이진 탐색을 수행합니다.
4. 찾는 값이 중간 위치보다 크면 오른쪽에서 이진 탐색을 수행합니다.

이진 탐색 과정

def binary_search(data, var):
  left=0
  right=len(data)-1

  while left<=right:
    mid = (left+right)//2
    if data[mid] == var:
      return mid
    elif data[mid] > var:
      right = mid-1
    elif data[mid] < var:
      left = mid+1

  return -1
data = [1, 3, 6, 7, 10, 14, 29, 45]
print(binary_search(data, 3))