[파이썬 알고리즘 인터뷰][이진검색] 이진 검색

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

배열에서 특정값 찾기

 

책에서 구현된 코드

# 반복문
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2

            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

# bisect
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)

        if index < len(nums) and nums[index] == target:
            return index
        else:
            return -1

 

기억해야할 기법

• 항상 재귀로 구현하는데, 반복문 구현 방식도 봐두기
• 탐색 중 값이 나오면 탐색 중지
  
  • mid값과 비교하여 같으면 중지
  • 이 때 mid값은 탐색에서 제외시키기
• bisect 사용

 

내가 구현한 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bs(l: int, r: int) -> int:
            if l == r:
                if nums[l] == target:
                    return l
                return -1

            mid = (l+r) // 2
            if target <= nums[mid]:
                return bs(l, mid)
            else:
                return bs(mid+1, r)
        return bs(0, len(nums)-1)

• bisect를 처음 알았다
• 이진 탐색도 간편하고, 삽입도 할 수 있다