이진 탐색은 정렬된 배열에서 원하는 value의 element를 O(logn) 이라는 좋은 성능으로 수행할 수 있는 알고리즘입니다.


문제 해결 방법은 간단합니다.


이미 정렬이 되어 있는 배열이기 때문에 배열중에 중간에 위치한 값을 체크해서 체크해야 하는 element들의 수를 반씩 줄이는 방법입니다.


import unittest
from typing import List


def binary_search(target: int, a: List[int]) -> int:
start, end = 0, len(a)
mid = (start + end) // 2
while 0 <= mid < len(a):
if target > a[mid]:
start = mid + 1
mid = (start + end) // 2
elif target < a[mid]:
end = mid - 1
mid = (start + end) // 2
else:
return mid

return -1


class TestCase(unittest.TestCase):
def test(self):
input_a = [i for i in range(100)]
target = 55
expected = 55

input_a2 = [i ** 2 for i in range(10)]
target2 = 81
expected2 = 9

input_a3 = [i ** 2 for i in range(10)]
target3 = -81
expected3 = -1

self.assertEqual(binary_search(target, input_a), expected)
self.assertEqual(binary_search(target2, input_a2), expected2)
self.assertEqual(binary_search(target3, input_a3), expected3)


코드를 보시면 보는 것 과 같이 가운데 값을 체크해서 원하는 값보다 크면 오른 쪽을 버리고,


작으면 왼쪽을 버리고 길이를 반으로 줄인 배열을 다시 같은 방법으로 줄여가면서 원하는 값을 찾습니다.


코드는 github으로도 확인하실수 있습니다.


https://github.com/baidoosik/ProblemSolving/blob/master/Search/binary_search.py



감사합니다.






+ Recent posts