문제65: 이진 검색

문제

입력

nums = [-1,0,3,5,9,12], target=9

출력

4

풀이

1. 재귀를 이용한 풀이

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)

1. 반복을 이용한 풀이

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

1. 모듈을 사용한 풀이

index = bisect.bisect_left(nums, target)

if index < len(nums) and nums[index] == target:
	return index
else:
	return -1

새로운 개념