이진 검색

 이진 검색은 값을 찾아내는 시간 복잡도가 O(log n)이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 탐색 트리와도 유사한 점이 많다. 그러나 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 '자료구조' 라면, 이진 검색은 정렬된 배열에서 값을 찾아내는 '알고리즘' 자체를 지칭한다.

 

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

Binary Search - LeetCode

 

 1. 재귀 풀이

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)

 

 2. 반복 풀이

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

 

 3. 이진 검색 모듈

 파이썬에서는 이진 검색을 직접 구현할 필요가 없다. 이진 검색 알고리즘을 지원하는 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