이진 탐색

https://youtu.be/94RC-DsGMLo

이 영상을 보며 작성하였습니다.

 

이진 탐색: 시작점, 끝점, 중간점의 위치를 나타내는 변수 3개를 이용함. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법.

#이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array,targrt,start,end):
	if start > end:
		return None
	mid = (start+end) // 2
	#찾은 경우 중간점 인덱스 반환
	if array[mid] == target:
		return mid
	#중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
	elif array[mid] > target:
		return binary_search(array,target,start,mid-1)
	#중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
	else:
		return binary_search(array,target,mid+1,end)

#n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
#전체 원소 입력 받기
array = list(map(int,input(),split()))

#이진 탐색 수행 결과 출력
result = binary_search(array,target,0,n-1)
if result == None:
	print(“원소가 존재하지 않습니다.”)
else:
	print(result+1)

    

#이진 탐색 소스코드 구현 (반복문)
def binary_search(array,target,start,end):
	while start <= end:
		mid = (start+end) // 2
		#찾은 경우 중간점 인덱스 반환
		if array[mid] == target:
			return mid
		#중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
		elif array[mid] > target:
			end = mid - 1
		#중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
		else:
			start = mid + 1
	return None

from bisect import bisect_left, bisect_right
bisect_left(a,x): 정렬된 순서를 유지하면서, 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환.
bisect_right(a,x): 정렬된 순서를 유지하면서, 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환.

# 값이 특정 범위에 속하는 데이터 개수 구하기
 
from bisect import bisect_left, bisect_right

#값이 [left_value,right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value,right_value):
	right_index = bisect_right(a, right_value)
	left_index = bisect_left(a, left_value)
	return right_index - left_index

a = […,…,…] #배열 선언

파라메트릭 서치: 최적화 문제를 결정 문제(‘예’ 혹은 ‘아니오’)로 바꾸어 해결하는 기법 (특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제). 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있음