Python 을 이용한 이진검색 / 파이썬, 리트코드 704.Binary Search

입력 값으로, 리스트를 받고 

Target에 해당하는 index값을 출력으로 반환하는 문제이다. 

이진검색이란? 

정렬된 배열에서 타겟을 찾는 검색 알고리즘이다. 

시간복잡도가 O(logn)이라는 점에서 대표적인 로그 시간 알고리즘이다 .

 

위의 문제를 4가지 방법으로 풀 수 있다. 

 

1.재귀 풀이

절반씩 범위를 줄여나가며 맞출 때까지 계속 재귀 호출을 하면된다. 

def search(self, num:List[int], target: int) -> int:
	def binary_search(left, right):
    # mid는 두 포인트의 중간지점
    	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
    # -1은 맨 끝 index를 의미            
       else:
           return -1
           
    return binary_search(0, len(nums) -1)

파이썬에는 재귀 호출에 대한 호출 횟수 제한이 존재한다.

 

2. 반복 풀이

재귀 풀이는 반복풀이로 변경할 수 있다. 재귀풀이는 우아한 편, 반복풀이는 직관적!

 

def search(self, num: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] - 1
        	right = mid -1
        
    else:
    	return mid
    return -1

 

3. 이진 검색 모듈

파이썬에서 제공하는 bisect 모듈을 이용 !! 

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

 

4. 이진 검색 사용X (코딩테스트에서는 지양하는 풀이법)

try:
	return num.index(target)
except ValueError:
	return -1

 

배열의 크기가 크고, 찾아야 하는 값이 항상 앞에만 있는 게 아니라면, 파이썬의 이진 검색 모듈인 bisect를 적극 활용하는 것이 좋다. 

(원래 bisect모듈은 리스트의 삽입 지점을 찾는 모듈이다!!)