내가 찾을 범위를 반으로 줄여가면서 빠르게 검색을 수행
🌐 검색과정
1. 자료의 중앙에 있는 원소 선택
2. 중앙 원소의 값과 목표 값 비교
3. 목표가 중앙 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색 수행
4. 목표 값을 찾을 때까지 위 과정을 반복
binarySearch(n, S[], key)
low <- 0
high <- n - 1
WHILE low <= high
mid <- low + (high - low) / 2
IF S[mid] == key
RETURN mid
ELIF S[mid] > key
high <- mid - 1
ELSE
low <- mid + 1
RETURN -1
arr = [2, 4, 7, 9, 11, 19, 23]
arr.sort()
def binarySearch(target):
low = 0
high = len(arr) - 1
# low > high 라면 데이터를 못찾은 경우
while low <= high:
mid = (low + high) // 2
# 1. 가운데 값이 정답인 경우
if arr[mid] == target:
return True
# 2. 가운데 값이 정답보다 작은 경우
elif arr[mid] < target:
low = mid + 1
# 3. 가운데 값이 정답보다 큰 경우
else:
high = mid - 1
return False
arr = [2, 4, 7, 9, 11, 19, 23]
arr.sort()
# 함수 한 번 호출할 때마다 low, high, 변수가 바뀌어서 사용됨
def binarySearch(low, high, target):
# 기저 조건 : 언제까지 재귀호출을 반복할 것인가?
# low > high라면 데이터를 못찾음
if low > high:
return -1
mid = (low + high) // 2
# 1. 가운데 값이 정답인 경우
if arr[mid] == target:
return mid
# 2. 가운데 값이 정답보다 작은 경우
elif arr[mid] < target:
return binarySearch(mid + 1, high, target)
# 3. 가운데 값이 정답보다 큰 경우
else:
return binarySearch(low, mid - 1, target)
return False