65. Binary Search

🎯 leetcode - 704. Binary Search

🤔 私の答え

📌 質問する

- 파이썬 알고리즘 인터뷰 65번 문제
- 이진 검색을 구현하라.

🤔 バイナリ検索とは?

📌 名前の日付

2020.02.28

📌 試行回数

1 try

💡 Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        ndict = defaultdict(int)
        for idx, n in enumerate(nums):
            ndict[n] = idx

        mid = len(nums) // 2
        while len(nums) > 0:
            if nums[mid] > target:
                nums = nums[:mid]
            elif nums[mid] < target:
                nums = nums[mid + 1 :]
            else:
                return ndict[nums[mid]]
            mid = len(nums) // 2
        return -1

💡 トラブルシューティング方法

- 반복문으로 이진 검색을 구현했다.
- 매 반복문마다 현재 nums[mid]값과 target값을 비교하여 문자열을 슬라이싱하여
검색할 대상 구간을 새롭게 갱신했다.
- 단, nums가 바뀌게 되면 index값을 구할 수 없게 되므로 초기 설정 시 ndict를 만들었다.
ndict는 값을 key로, 인덱스를 value로 갖는 딕셔너리이다.
- 따라서 최종적으로 값을 찾으면 해당 값의 인덱스를 딕셔너리에서 구해 반환할 수 있다.

💡 新知

- 이진 검색 개념에 대해 새롭게 알게 되었다. (이진 검색에 대한 설명은 상단에 정리해두었다.)

答えを間違える理由

- 

😉 別の解釈

📌 一つ。より簡潔な複文解答

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            # mid = (left + right) // 2		# 이렇게 풀어도 되지만 오버플로 문제가 발생할 수 있음
            mid = left + (right - left) // 2 	# <-- 오버플로를 피하면서 정확한 mid값을 구할 수 있다.
            
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1

💡 トラブルシューティング方法

- 이번에는 nums를 직접 슬라이싱하지 않고 left, right라는 인덱스만 변하면서 반복문으로 풀이했다.
- 이게 좀 더 좋은 풀이인 것 같다. 그리고 훨씬 빠르다.

💡 新知

- 일부 자료형이 엄격한 언어에서는 
> mid = (left + right) // 2
를 수행했을 때 오버플로가 발생하기도 한다.
- 이를 해결하기 위해 아래와 같이 작성하는 게 좀 더 정확하고 좋은 방법이다.
> mid = left + (right - left) // 2

📌 二。さいきか

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search(left, right):
            if left <= right:
                mid = (left + right) // 2

                if nums[mid] < target:
                    return binary_search(mid + 1, right)
                elif nums[mid] > target:
                    return binary_search(left, mid - 1)
                else:
                    return mid
            else:
                return -1  # 탐색이 끝나도 값을 찾지 못한 경우

        return binary_search(0, len(nums) - 1)

💡 トラブルシューティング方法

- 반복문에서 left, right의 값을 바꾸어 구간을 조정한 것을 재귀로 처리하고
최종적으로 값을 찾은 경우 mid값을 리턴했다는 차이점만 있다.
- return mid(또는 return -1)을 해도
한번 mid(또는 -1)가 리턴되면 처음 리턴문까지 똑같은 값이 리턴된다.
- 잘 이해가 안되면 아래 링크로 직접 확인해보자.

💡 新知

-

📌 三。バイナリサーチモジュール

import 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
        return -1

💡 トラブルシューティング方法

- 파이썬에서는 이진 검색 알고리즘을 지원하는 bisect 모듈을 기본으로 제공한다.

💡 新知

- bisect.bisect_left(list, target)
> 정렬된 list에 target를 삽입할 위치를 리턴해준다. 
> target이 list에 이미 있으면 기존 항목의 앞(왼쪽)의 위치를 반환한다.
> target이 list에 없으면 맨 끝 인덱스를 반환한다.

- bisect_right는 반대로 target이 list에 이미 있으면 기존 항목의 뒤(오른쪽)의 
위치를 반환한다.