[Python][LeetCode] Binary Search(이진탐색)

https://leetcode.com/problems/binary-search/description/

Binary Search - LeetCode

 

문제설명:

정렬된 리스트를 입력받아 이진검색으로 target에 해당하는 인덱스를 구하는 문제

 

이진탐색, 재귀로 구현

• mid 값은 지정해준다.
• 리스트의 중간값이 타겟과 같으면 반환해준다.
• 리스트의 중간값이 타겟보다 작으면
  • left -> mid+1로 바꿔 재귀
• 리스트의 중간값이 타겟보다 크면
  • right -> mid-1로 바꿔 재귀

        idx = 0
        def bs(lst, target, start, end):
            nonlocal idx
            if start == end:
                idx = -1
                return idx

            mid = (start + end) // 2
            if lst[mid] == target:
                idx = mid
                return idx
            else:
                if lst[mid] < target:
                    bs(lst, target, mid+1, end)
                else:
                    bs(lst, target, start, mid)

            return idx

        result = bs(nums, target, 0, len(nums))
        return result