플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤
from typing import List
def binsearch(L: List, target: int, left: int, right: int) -> int:
if left > right:
return -1
else:
mid = (left + right) // 2
if L[mid] < target:
left = mid + 1
elif L[mid] > target:
right = mid - 1
else:
return mid
return binsearch(L, target, left, right)
(1) 음수일 때
ex) [1, 4, 6]
이라면, -100
은 없는 숫자다.
(2) 리스트 범위 내의 존재하지 않는 수일 때
ex) [1, 4, 6]
이라면, 5
는 없는 숫자다.
(3) 리스트 내 가장 큰 수보다 큰 숫자일 때
ex) [1, 4, 6]
이라면, 100
은 없는 숫자다.
import unittest
from typing import List
def binsearch(L: List, target: int, left: int, right: int) -> int:
if left > right:
return -1
else:
mid = (left + right) // 2
if L[mid] < target:
left = mid + 1
elif L[mid] > target:
right = mid - 1
else:
return mid
return binsearch(L, target, left, right)
class 해가_존재하는_이진탐색(unittest.TestCase):
def test_타켓_2가_첫_번째_인덱스이므로_0을_리턴해야_한다(self):
L = [2, 3, 5, 6, 9, 11, 15]
target = 2
left = 0
right = len(L) - 1
answer = 0
self.assertEqual(binsearch(L, target, left, right), answer)
def test_타켓_15가_마지막에_있으므로_인덱스_6을_리턴해야_한다(self):
L = [2, 3, 5, 6, 9, 11, 15]
target = 15
left = 0
right = len(L) - 1
answer = 6
self.assertEqual(binsearch(L, target, left, right), answer)
def test_타켓_3이_두_번째_인덱스이므로_1을_리턴해야_한다(self):
L = [2, 3, 5, 6, 9, 11, 15]
target = 3
left = 0
right = len(L) - 1
answer = 1
self.assertEqual(binsearch(L, target, left, right), answer)
def test_타켓_15가_마지막에_있으므로_인덱스_6을_리턴해야_한다(self):
L = [2, 3, 5, 6, 9, 11, 15]
target = 15
left = 0
right = len(L) - 1
answer = 6
self.assertEqual(binsearch(L, target, left, right), answer)
class 해가_존재하지_않는_이진탐색(unittest.TestCase):
def test_타켓_minus_100은_리스트에_없으므로_minus_1을_리턴해야_한다(self):
L = [2, 3, 5, 6, 9, 11, 15]
target = -100
left = 0
right = len(L) - 1
answer = -1
self.assertEqual(binsearch(L, target, left, right), answer)
def test_타켓_7은_리스트에_없으므로_minus_1을_리턴해야_한다(self):
L = [2, 3, 5, 6, 9, 11, 15]
target = 7
left = 0
right = len(L) - 1
answer = -1
self.assertEqual(binsearch(L, target, left, right), answer)
def test_타켓_100은_리스트에_없으므로_minus_1을_리턴해야_한다(self):
L = [2, 3, 5, 6, 9, 11, 15]
target = 100
left = 0
right = len(L) - 1
answer = -1
self.assertEqual(binsearch(L, target, left, right), answer)
if __name__ == '__main__':
unittest.main()