64 — 이진 탐색 — 절반씩 찾기

62 가이드가 목록을 정렬했고, 39 가이드가 Python으로 정렬하게 했습니다. 목록이 정렬되면 더 똑똑한 검색 방법이 등장합니다. 이진 탐색은 값을 왼쪽부터 오른쪽으로 확인하는 대신 가운데 값을 읽고, 비교 결과로 남은 범위의 절반을 통째로 버립니다 — 1000개짜리 목록도 최대 10번의 추측이면 됩니다.

#단계

1. 낮은과 높은이라는 두 포인터가 목표가 있을 수 있는 범위를 가둡니다. 중간은 그 범위의 가운데이고, //는 나누고 내림합니다:

   숫자들 = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
   낮은 = 0
   높은 = len(숫자들) - 1
   중간 = (낮은 + 높은) // 2
   말해 f"낮은={낮은} 높은={높은} 중간={중간} 추측={숫자들[중간]}"
   

   복사실행해 보기 →

   낮은=0 높은=9 중간=4 추측=16이 출력됩니다. 값 10개에서 가운데는 인덱스 4, 숫자 16입니다.

2. 추측을 목표와 비교합니다. 너무 작으면 중간 왼쪽의 모든 값도 너무 작으므로 낮은이 그 다음으로 뛰어넘습니다. 너무 크면 높은이 그 아래로 뛰어내립니다. 이것을 반복하면 매 루프마다 범위가 절반으로 줄어듭니다:

   숫자들 = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
   목표 = 23
   낮은 = 0
   높은 = len(숫자들) - 1
   단계 = 0
   찾음 = -1
   
   동안 낮은 <= 높은:
       단계 = 단계 + 1
       중간 = (낮은 + 높은) // 2
       말해 f"단계 {단계}: 중간={중간} 추측={숫자들[중간]}"
       if 숫자들[중간] == 목표:
           찾음 = 중간
           break
       if 숫자들[중간] < 목표:
           낮은 = 중간 + 1
       else:
           높은 = 중간 - 1
   
   if 찾음 != -1:
       말해 f"인덱스 {찾음}에서 {목표} 값을 찾았습니다"
   else:
       말해 f"목록에 {목표} 값이 없습니다"
   

   복사실행해 보기 →

   찾음 = -1은 "아직 못 봤다"라는 표시입니다. 빗나가면 절반씩 줄이고, 맞히면 인덱스를 기록하고 break로 나옵니다.

3. 목표 23을 따라가 보겠습니다. 먼저 중간=4가 16을 추측하고, 16 < 23 이므로 16과 그 왼쪽 모두 너무 작아 낮은이 5가 됩니다. 범위가 열 값에서 다섯 값으로 줄었습니다. 다음 중간=7이 56을 추측하고, 56 > 23이므로 그 오른쪽이 모두 너무 커서 높은이 6이 됩니다. 두 값이 남았습니다. 중간=5가 정확히 23을 추측합니다. 세 단계 만에 인덱스 5에서 찾았습니다.

4. 전체 프로그램입니다. 매 단계를 출력하고, 찾은 인덱스, 단계 수, 그리고 비교용 왼쪽에서 오른쪽 검색을 보여 줍니다. binary.ko.nme로 저장합니다:

   # binary.ko.nme — 이진 탐색, 절반씩 찾기
   # 실행: nme 실행 binary.ko
   #
   # 목록이 정렬되어 있습니다. 낮은과 높은이라는 두 포인터로
   # 목표가 있을 수 있는 범위를 잡고, 매 단계 가운데를 읽어
   # 목표와 비교한 뒤 범위의 절반을 버립니다.
   
   숫자들 = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
   목표 = 23
   
   낮은 = 0
   높은 = len(숫자들) - 1
   단계 = 0
   찾음 = -1
   
   동안 낮은 <= 높은:
       단계 = 단계 + 1
       중간 = (낮은 + 높은) // 2
       추측 = 숫자들[중간]
       말해 f"단계 {단계}: 낮은={낮은} 높은={높은} 중간={중간} 추측={추측}"
       if 추측 == 목표:
           찾음 = 중간
           break
       if 추측 < 목표:
           낮은 = 중간 + 1
       else:
           높은 = 중간 - 1
   
   말해 ""
   if 찾음 != -1:
       말해 f"인덱스 {찾음}에서 {목표} 값을 {단계}단계 만에 찾았습니다"
   else:
       말해 f"목록에 {목표} 값이 없습니다 ({단계}단계)"
   말해 f"범위가 {len(숫자들)}개 값에서 1개로 줄었습니다"
   
   선형 = 0
   for i in range(len(숫자들)):
       선형 = 선형 + 1
       if 숫자들[i] == 목표:
           break
   말해 f"왼쪽에서 오른쪽으로 찾으면 {선형}개를 확인합니다"
   

   복사실행해 보기 →

5. 실행합니다:

   nme 실행 binary.ko
   

   복사

   단계 1: 낮은=0 높은=9 중간=4 추측=16
   단계 2: 낮은=5 높은=9 중간=7 추측=56
   단계 3: 낮은=5 높은=6 중간=5 추측=23
   
   인덱스 5에서 23 값을 3단계 만에 찾았습니다
   범위가 10개 값에서 1개로 줄었습니다
   왼쪽에서 오른쪽으로 찾으면 6개를 확인합니다
   

   복사

   세 번의 추측으로 23을 찾은 반면, 왼쪽에서 오른쪽 검색은 여섯 번 확인해야 했습니다. 루프마다 범위는 계속 절반으로 줄어듭니다 — 값 열 개, 다섯 개, 두 개, 그다음 한 개. 단계 수가 바로 검색의 비용입니다.

6. 영어는 같은 단계를 while, show, 영어 변수 이름으로 씁니다. 전체 영어 프로그램은 영어 가이드에 있습니다.

#직접 해보기

목표를 5(왼쪽 끝 가까이)로 바꾸고 다시 실행해 보세요 — 두 단계면 됩니다. 그런 다음 목록에 없는 40을 시도해 보세요. 루프가 범위를 다 써서 "목록에 없습니다"를 출력하고 몇 단계가 필요했는지 알려 줍니다. 목록을 처음 100개 숫자 list(range(1, 101))로 바꾸고 목표 = 23을 유지해 보세요. 범위가 여전히 절반씩 줄어들므로 추측 수는 거의 늘지 않습니다.

#배운 것

• 낮은과 높은이 목표가 있을 수 있는 범위를 가둡니다.
• 중간 = (낮은 + 높은) // 2가 가운데를 고릅니다. //는 내림합니다.
• 추측을 비교하면 범위가 절반이 됩니다 — 왼쪽에서 빗나가면 왼쪽 절반을 버립니다.
• break는 목표를 찾는 순간 루프를 나갑니다.
• 이진 탐색은 목록이 먼저 정렬되어 있어야 합니다.