[TIL-250523] 이진탐색

이진탐색이란?

  - 둘로 나눠 탐색하는 방법을 일컫는다. 즉, 정렬된 데이터에서 원하는 값을 찾기 위해 범위를 계속 반으로 좁혀가는 방법

   *주의 할 점은 정렬되어야 한다는 것

 

기본구조

def binary_search(arr, target):     start = 0     end = len(arr) - 1     while start <= end:         mid = (start + end) // 2         if arr[mid] == target:             return mid  # 찾은 위치의 인덱스 반환         elif arr[mid] < target:             start = mid + 1  # 오른쪽 탐색         else:             end = mid - 1  # 왼쪽 탐색     return -1  # 못 찾은 경우

 

예시)

arr = [ 2,4,7,9,12,15,20] target = 12

arr 리스트에서 12라는 값을 찾고 싶다고 할때 브루트포스 방식으론, 하나씩 인덱스를 비교하며 찾아야한다.

 

이진탐색 

 

arr = [2, 4, 7, 9, 12, 15, 20]           ↑          ↑               ↑        start      mid          end

 처음엔 Start = 0, end =6(리스트길이 -1)

  mid =(start + end) // 2

    = (0+6) // 2 = 3 

즉 mid 값은 9가 되는 것!

 

- 우리가 찾는 값은 12는 9보다 크니까 오른쪽에 있을 것이다.

   start = mid + 1  = 4 그래서 스타트 인덱스를 옮겨 12부터 탐색한다.

arr = [2, 4, 7, 9, 12, 15, 20]                            ↑      ↑                         start   end

• 다시 mid = (4 + 6) // 2 = 5
• arr[5] = 15 → 너무 크다! 12보다 작아야 한다.  → end = mid - 1 = 4

arr = [2, 4, 7, 9, 12, 15, 20]                            ↑                     start=end=4

 

 

핵심요약

용어 의미

start	탐색 구간의 왼쪽 끝 인덱스
end	탐색 구간의 오른쪽 끝 인덱스
mid	start와 end의 중간 인덱스
target	우리가 찾고자 하는 값
조건	arr[mid] == target이면 정답

 

---

🛠️ 어디에 쓰일까?

• 정렬된 데이터에서 값이 있는지 확인
• 파라메트릭 서치 (범위를 설정해서 최적값 찾기)
• 문제: 백준 1920, 1654, 2805, 2110 등

---

📚 마지막 정리!

 

초기 상태:         2  4  7  9  12  15  20                                      ↑                           mid=3 (arr[3]=9) 1단계 후:                  12  15  20                                         ↑                              mid=5 (arr[5]=15) 2단계 후:                  12                                   ↑                            mid=4 (arr[4]=12)