[Algo] 이진 탐색

1. 개념

학창 시절에 했던 업다운 게임과 유사하다.

업다운

Alice : 내 나이 맞춰봐
Bob : 20?
Alice : Up

Bob : 30?
Alice : Down
Bob : 25!

Alice: 정답

---

2. 동작 과정

데이터의 시작점 = head
데이터의 끝점 = tail
데이터의 중간 = (head + tail) / 2

1. 데이터 중간 지점에서의 값과 찾고자 하는 값이 같은지 체크

2-1. 찾고자 하는 값이 작으면 tail을 ( 중간지점 - 1 ) 위치로 이동

2-2. 찾고자 하는 값이 크면 head를 ( 중간지점 + 1) 위치로 이동

3. 반복한다

---

3. Code

def binary_search(data, target):


  start = 0
  end = len(data) - 1

  while start <= end:

    mid_point = round((start + end) / 2)

    if data[mid_point] == target:
      return data[mid_point]

    elif data[mid_point] < target:
      start = mid_point + 1
    
    else:
      end = mid_point - 1
      


data = [ x for x in range(1, 25123)]
target = 5234

import time
t1 = time.time()
print(binary_search(data, target))
t2 = time.time()

print(f"실행시간 : {t2 - t1:.8f}")