[알고리즘 in python] 이분 탐색 (Binary Search)

이분 탐색 (Binary Search) 이란?

• 정렬된 리스트에서 특정한 값을 빠르게 찾기 위한 알고리즘
• 반으로 나누는 전략을 사용하여 검색 범위를 좁혀 나감 -> $O(log n)$ 의 시간 복잡도 가짐

---

알고리즘 설명

1. 초기화

• 리스트의 시작 인덱스 ('left')와 끝 인덱스('right') 설정
• 'left'는 0, 'right'는 리스트의 마지막 인덱스로 초기화

2. 반복

• 'left'가 'right'보다 작거나 같은 동안 다음을 반복
  1. 중앙 인덱스 ('mid') 계산 : 'mid' = (left + right) // 2
  2. 리스트의 중앙 값과 찾고자 하는 값 비교
     • 중앙 값 == 찾고자 하는 값 : 인덱스 반환
     • 중앙 값 > 찾고자 하는 값 : 'right' = 'mid' - 1
     • 중앙 값 < 찾고자 하는 값 : 'left' = 'mid' + 1

3. 종료

• 'left'가 'right' 보다 커지면, 리스트에 찾고자 하는 값이 없음을 의미
• 이러한 경우, 검색 실패를 나타내는 값 반환 (-1, None 등)

---

구현 예제

def binary_search(arr, target):
	left, right = 0, len(arr) - 1
    
    while left <= right:
    	mid = (left + right) // 2
        
        if arr[mid] == target:
        	return mid
        elif arr[mid] < target:
        	left = mid + 1
        else:
        	right = mid - 1
    
	return -1

---

대표 문제 유형

1. 정렬된 배열에서 특정 값 찾기
2. 정렬된 배열에서 삽입 위치 찾기
3. 최대 혹은 최소 값 찾기 (특정 조건을 만족하는 범위 내의 최대 길이 찾기)
   • 일정 길이 이상인 나무 자르기, 랜선 자르기 등
4. 정렬된 배열에서 첫 번째 또는 마지막 발생 위치 찾기
5. 목표 값과 가장 가까운 값 찾기
6. 제곱근 찾기
7. 피크 요소(좌우 인접 값보다 큰 값) 찾기