반응형
1.
다음은 가장 잘 알려진 이진 검색 코드다.
찾으려는 값을 target으로 넣어주면 그 값에 해당하는 인덱스를 빠르게 찾아 리턴한다.
a= [1,4,5,8,12]
def binary_search(target):
left = 0
right = len(a)-1
while left <= right:
mid = (left+right)//2
if a[mid] == target: #find
return mid
elif a[mid] > target:
right = mid -1
else:
left = mid + 1
return mid
print('target:',4, 'find:',a[binary_search(4)])
print('target:',5, 'find:', a[binary_search(5)])
print('target:',8, 'find:', a[binary_search(8)])
print('target:',12, 'find:', a[binary_search(12)])
>> target: 4 find: 4
>> target: 5 find: 5
>> target: 8 find: 8
>> target: 12 find: 12
2.
그러면 동일한 코드인데 리스트에 존재하지 않는 값을 찾으면 어떻게 될까?
다음을 확인해보자.
a= [1,4,5,8,12]
def binary_search(target):
left = 0
right = len(a)-1
while left <= right:
mid = (left+right)//2
if a[mid] == target: #find
return mid
elif a[mid] > target:
right = mid -1
else:
left = mid + 1
return mid
print('target:',0, 'find:',a[binary_search(0)])
print('target:',2, 'find:', a[binary_search(2)])
print('target:',6, 'find:', a[binary_search(6)])
print('target:',13, 'find:', a[binary_search(13)])
>> target: 0 find: 1
>> target: 2 find: 4
>> target: 6 find: 8
>> target: 13 find: 12위의 결과를 살펴보면, 존재 하지 않는 값을 찾으려고 시도할때 그 근처의 값을 찾아 변환해주는 것을 볼 수 있다.
정확히 살펴보면
1. 리스트의 최솟값보다 더 작은 값을 찾으려고 시도 -> 리스트의 첫번째 값을 찾음
2. 리스트의 최댓값보다 더 큰 값을 찾으려고 시도 -> 리스트의 마지막 값을 찾음
3. 리스트의 최솟값, 최댓값 사이의 값이지만 존재하지 않는 값을 찾으려고 시도 -> 그 값보다 크면서 가장 가까운 값을 찾음
3.
다음으로 밑의 코드는 존재 하지 않는 값을 찾으려고 시도할 때 mid값이 아닌 right값을 리턴해주는 경우이다.
결과를 살펴보자.
a= [1,4,5,8,12]
def binary_search(target):
left = 0
right = len(a)-1
while left <= right:
mid = (left+right)//2
if a[mid] == target: #find
return mid
elif a[mid] > target:
right = mid -1
else:
left = mid + 1
return right ########## mid 대신에 right
print('target:',0, 'find:',a[binary_search(0)])
print('target:',2, 'find:', a[binary_search(2)])
print('target:',6, 'find:', a[binary_search(6)])
print('target:',13, 'find:', a[binary_search(13)])
>> target: 0 find: 12
>> target: 2 find: 1
>> target: 6 find: 5
>> target: 13 find: 12
정확히 살펴보면
1. 리스트의 최솟값보다 더 작은 값을 찾으려고 시도 -> 인덱스 -1를 반환하여 리스트 마지막 값을 찾게 됨
2. 리스트의 최댓값보다 더 큰 값을 찾으려고 시도 -> 리스트의 마지막 값을 찾음
3. 리스트의 최솟값, 최댓값 사이의 값이지만 존재하지 않는 값을 찾으려고 시도 -> 그 값보다 작으면서 가장 가까운 값을 찾음
1의 문제를 보완해주기 위해 max(right,0)을 리턴해주는 편이 낫다.
a= [1,4,5,8,12]
def binary_search(target):
left = 0
right = len(a)-1
while left <= right:
mid = (left+right)//2
if a[mid] == target: #find
return mid
elif a[mid] > target:
right = mid -1
else:
left = mid + 1
return max(right, 0)
print('target:',0, 'find:',a[binary_search(0)])
print('target:',2, 'find:', a[binary_search(2)])
print('target:',6, 'find:', a[binary_search(6)])
print('target:',13, 'find:', a[binary_search(13)])
>> target: 0 find: 1
>> target: 2 find: 1
>> target: 6 find: 5
>> target: 13 find: 12
4.
left의 경우 결과는 다음과 같다.
인덱스 오류를 피하기위해 min(left, len(a)-1)을 해주면 사실상 mid랑 다를게 없어진다.
a= [1,4,5,8,12]
def binary_search(target):
left = 0
right = len(a)-1
while left <= right:
mid = (left+right)//2
if a[mid] == target: #find
return mid
elif a[mid] > target:
right = mid -1
else:
left = mid + 1
return min(left, len(a)-1)
print('target:',0, 'find:',a[binary_search(0)])
print('target:',2, 'find:', a[binary_search(2)])
print('target:',6, 'find:', a[binary_search(6)])
print('target:',13, 'find:', a[binary_search(13)])
>> target: 0 find: 1
>> target: 2 find: 4
>> target: 6 find: 8
>> target: 13 find: 12
댓글