이진탐색

플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤

---

1. 재귀 알고리즘을 활용한 이진탐색 구현

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)

---

2. 검증 시나리오

1) 해가 있는 경우

• (1) 타켓 숫자가 첫 번째 인덱스일 때
• (2) 타켓 숫자가 마지막 인덱스일 때
• (3) 타켓 숫자가 첫 번째도, 마지막 인덱스도 아닐 때

2) 해가 존재하지 않는 경우

• (1) 음수일 때
  ex) [1, 4, 6] 이라면, -100은 없는 숫자다.

• (2) 리스트 범위 내의 존재하지 않는 수일 때
  ex) [1, 4, 6] 이라면, 5는 없는 숫자다.

• (3) 리스트 내 가장 큰 수보다 큰 숫자일 때
  ex) [1, 4, 6]이라면, 100은 없는 숫자다.

---

3. 테스트 코드

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()

---

4. 테스트 결과