[이코테] 이진탐색-정렬된 배열에서 특정 수의 개수 구하기

• 순차 탐색 : 앞에서부터 단순히 데이터를 찾기위해 하나씩 확인하는 방법
• 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

이진 탐색 시간 복잡도
단계마다 탐색 범위를 2로 나누는 것과 동일하기에 log2 N에 비례하다.
예를 들어 32개에서 1단계 거치면 16개 데이터만 남고, 그 뒤에 8개, 4개 데이터만 남는다. 즉 탐색범위를 절반씩 줄이며 시간복잡도는 O(logN)을 보장한다.

따라서 데이터 수나 탐색범위가 1000만 단위 이상으로 넘어가면 이진탐색으로 문제에 접근하자!

# 이진탐색 구현 재귀함수
def binary_search(array,target, 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=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) # 인덱스값 나오기때문에 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

파이썬 이진 탐색 라이브러리

• bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a,x) : bisect_left와 거의 같은 함수인데, 이번에는 x가 a에 이미 있으면 기존 항목 뒤 (오른쪽)의 위치를 반환한다.

정렬된 배열에서 특정 수의 개수 구하기

-> 선형 탐색으로는 시간 초과 판정을 받는다.

from bisect import bisect_left, bisect_right
def count_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=[1,2,3,3,3,4,6,7]
print(count_range(a,4,4)) # 값이 4인 데이터 개수 출력
print(count_range(a,-1,4)) # 값이 -1,4 범위에 있는 데이터 개수 출력

• 파라메트릭 서치
  최적화 문제를 결정문제(예/아니오)로 바꾸어 해결하는 기법
  이진탐색을 이용해 해결할 수 있다.