이진 탐색은 일반적으로 이렇게 짠다.
def binary_search(arr, target):
left = 0
right = 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. 종료 조건
- 종료 조건은 인덱스가 left > right일 때이다. (즉 반복 조건은left <= right )
- left < right로 반복 조건을 짤 경우, left == right 가 되면, 찾고자 하는 값이 배열에 없을 경우 무한 루프에 빠질 수 있다.
2. 갱신 조건
위처럼 left, right 를 갱신하는 게 일반적이지만..
2.1. 중복 값중 가장 왼쪽/오른쪽 인덱스 찾기
중복된 값 중 가장 왼쪽을 찾고 싶거나, 가장 오른쪽을 찾고 싶은 경우는 아래처럼 구현한다.
공통적으로 left < right (기존에는 left <= right )
가장 왼쪽 찾기 : right 갱신 조건에서 mid - 1 대신 mid
가장 오른족 찾기 : left 갱신 조건에서 mid + 1 대신 mid
가장 왼쪽 인덱스 값 찾기
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left if arr[left] == target else -1
가장 오른쪽 인덱스 값 찾기
while left < right:
mid = (left + right + 1) // 2
if arr[mid] > target:
right = mid - 1
else:
left = mid
return left if arr[left] == target else -1
'Work, Study > 코테, 알고리즘' 카테고리의 다른 글
[백준](Python, TypeScript) 1018번 : 체스판 다시 칠하기 (0) | 2024.07.24 |
---|---|
[백준, Python] 1463 - 1로 만들기 (0) | 2024.07.24 |
[Python] 힙 (0) | 2024.07.24 |
[Python] DFS, BFS (0) | 2024.07.24 |
[Python] n까지의 소수 구하기 - 에라토스테네스의 체 (0) | 2024.07.24 |