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)가 리턴되면 처음 리턴문까지 똑같은 값이 리턴된다.
- 잘 이해가 안되면 아래 링크로 직접 확인해보자.

• 재귀로 푸는 방법 이해하기

💡 새롭게 알게 된 점

-

📌 셋. 이진 검색 모듈 bisect

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에 이미 있으면 기존 항목의 뒤(오른쪽)의 
위치를 반환한다.