[23일차] TIL 이진 탐색(Binary Search) - (1)

이진탐색이란

정렬되어있는 배열에서 절반씩 줄여가며 탐색하는 기법입니다. 정렬되어있다는 전제가 필요하며 수행했을 시 1억 개 목록을 탐색한다면 27번 안에 찾을 수 있다.

 

직접 구현하는 방법도 있지만, 파이썬 내장함수인 bisect_left 를 사용해도 됩니다. bisect_right도 있지만 가장 많이 사용되는 것이 bisect_left 입니다. 

bisect_left는 target값의 index를 반환하는 반면 bisect_right는 index + 1값을 반환하게 됩니다. 따라서 특별한 경우가 아니라면 bisect_left를 가장 많이 사용하게 될것입니다.

 

1. leetcode 704

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

leetcode 704번 문제입니다. 문제자체는 단순하지만 조건에 O(logN)의 시간복잡도를 가지라고 하기에 이진탐색을 유도한 문제입니다.

bisect_left를 사용하였습니다.

 

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        idx = bisect.bisect_left(nums, target)
        
        if idx < len(nums) and nums[idx] == target:
            return idx
        else:
            return -1

 

2. leetcode 33

https://leetcode.com/problems/search-in-rotated-sorted-array/

처음 주어지는 배열의 길이가 정렬되지 않은 배열입니다. 완전히 뒤섞인 배열은 아니고 정렬된배열이 두 부분으로 나뉜 배열입니다. 이를 해결하기 위해서는 어느 부분부터 정렬되지 않았는지를 판단하는 것이 중요합니다. 정렬되지 않는 부분부터 배열의 앞까지를 똑 떼서 뒤에 붙인 후 이진 탐색을 수행하는 것이 아이디어였습니다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bs(lst, start, end):
            if start > end:
                return -1
            
            mid = (start + end) // 2
            if lst[mid] < target:
                return bs(lst, mid + 1, end)
            elif lst[mid] > target:
                return bs(lst, start, mid - 1)
            else:
                return mid

        
        if not nums:
            return -1
        
        left = 0
        right = len(nums) - 1
        
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        
        # 정렬되지 않은부분을 떼어서 뒤에 붙임
        added = nums + nums[:left]
        print(added)
        
        result = bs(added, left, len(added) - 1)
        print(result)
        
        # 탐색부분이 left 부터 끝까지 이므로 index는 기존 배열의 길이만큼 나눈 나머지입니다.
        return result if result == -1 else result % len(nums)