07) 이진탐색

Python/[책] 이코테

07) 이진탐색

spring_sunshine 2022. 6. 14. 15:39

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용한다.
- 리스트에 특정 값의 원소가 있는지 체크할 때
- 리스트에 특정 값이 원소의 개수를 세는 count() 메서드를 이용할 때

이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
찾으려는 데이터와 중간점에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

이진 탐색의 시간 복잡도

한 번 탐색할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도는 O(logN)이다. (=퀵정렬)

이진 탐색 구현 방법

1. 재귀함수 이용

# 이진탐색 재귀함수 구현
def bin_search(arr, target, start, end):
	if start > end:
    	return None
    mid = (start+end)//2 #중간점
    
    # 찾은 경우 중간점 index 반환
    if arr[mid] == target:
    	return mid 
    # 중간점보다 target이 작은 경우 중간점의 왼쪽 범위로 축소
    elif arr[mid] > target:
    	return bin_search(arr, target, start, mid-1)
    # 중간점보다 target이 큰 경우 중간점의 오른쪽 범위로 축소 
    else:
    	return bin_search(arr, target, mid+1, end)

# 데이터 입력
n,target = list(map(int,input().split()))
arr = list(map(int,input().split()))

# 수행결과 출력 
result = bin_search(arr, target, 0, n-1)
if result==None:
	print("원소가 존재하지 않습니다")
else:
	print(result+1)

2. 반복문 이용

# 이진탐색 반복문 구현
def bin_search(arr, target, start, end):
	while start <= end:
    	mid = (start+end)//2
        
        if arr[mid] == target:
        	return mid
        elif arr[mid] > target:
        	end = mid-1 # 왼쪽 확인
        else:
        	start = mid+1 # 오른쪽 확인
    return None
    
n,target = list(map(int,input().split()))
arr = list(map(int,input().split()))

result = bin_search(arr, target, 0, n-1)
if result == None:
	print("원소가 존재하지 않습니다")
else:
	print(result+1)

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

bisect_left(iterable,value): 배열의 정렬된 순서를 유지하면서 value를 삽입할 가장 왼쪽 인덱스를 반환
bisect_right(iterable,value): 배열의 정렬된 순서를 유지하면서 value를 삽입할 가장 오른쪽 인덱스를 반환
c++의 upper_bound, lower_bound와 동일함

from bisect import bisect_left, bisect_right
nums = [0,1,2,3,4,5,6,7,8,9]
n = 5

print(bisect_left(nums, n))
print(bisect_right(nums, n))

'''
결과값
5
6
'''

파라메트릭 서치 (Parametric Search)

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

트리 자료구조

이진 탐색의 전제 조건은 데이터 정렬이며, 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다.
트리 자료구조는 노드와 노드의 연결로 표현하며, 노드는 어떠한 정보를 갖고 있는 개체로 정보의 단위이다.
- 트리는 부모노드와 자식노드의 관계로 표현된다.
- 트리의 최상단 노드는 루트노드이다.
- 트리의 최하단 노드는 단말노드이다.
- 트리에서 일부를 떼어내도 트리 구조이며, 이를 서브트리라고 한다.
- 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

이진 탐색 트리

트리 구조 중 가장 간단한 형태는 이진 탐색트리이다.
이진 탐색트리는 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조이다.
이진 탐색트리는 왼쪽 자식노드 < 부모노드 < 오른쪽 자식노드의 특징을 가진다.

#1 부품 찾기

이진탐색 구조 제대로 기억하기!

N=int(input())
all=list(map(int,input().split()))
M=int(input())
request=list(map(int,input().split()))

#이진탐색 이용
def bin_search(all,target,s,e):
  while s<=e:
    mid = (s+e)//2 
    if all[mid]==target:
      return 1
    elif all[mid] > target:
      e = mid-1
    else:
      s = mid+1
  return 0
    
all.sort() #오름차순 2 3 7 8 9
s = 0
e = N-1 # all 길이
for x in request:
  ans = bin_search(all,x,s,e)
  if ans==0:
    print("no",end=" ")
  else:
    print("yes",end=" ")

#2 떡볶이 떡 만들기

'현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤, 조건의 만족 여부에 따라 탐색 범위를 좁혀서 해결할 수 있다.
절단기의 높이는 0~10억까지의 정수 중 하나이고, 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 한다.
끝점: 가장 긴 떡의 길이 / 시작점:0 으로 설정하고 탐색 시작

N,M = map(int,input().split())
height = list(map(int,input().split()))

start=0
end = max(height)

#이진탐색 구현하기
result=0
while (start<=end):
	total=0
    mid = (start+end)//2
    
    for x in height:
    	# 떡이 잘릴 경우만 (x>mid)
        if x>mid: total += x-mid
        
    # 떡이 부족한 경우 (왼쪽 탐색)
    if total<M:
    	end = mid-1
    
    # 떡이 충분한 경우 (오른쪽 탐색)
    else:
    	result = mid
        start = mid+1
        

print(result)

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

시간복잡도 O(logN)을 요구하므로 이진탐색을 수행해야 한다.
특정 값이 등장하는 첫번째 위치와 마지막 위치를 찾아 위치 차이를 계산하여 문제를 해결할 수 있다.

[내 풀이] - 완성x

#N개의 원소를 포함한 수열 오름차순 정렬
#x가 등장하는 횟수 구하기
#O(logN)
N,x = map(int,input().split())
arr = list(map(int,input().split()))

start=0
end=N-1
cnt=0

#이진탐색
while (start<=end):
  mid=(start+end)//2
  if arr[mid]==x:
    fs=fe=mid
  elif arr[mid] > x:
    end=mid-1
  else:
    start=mid+1

if cnt==0: print(-1)
else: print(cnt)

[정답 풀이]

from bisect import bisect_left,bisect_right

#값이 [left_val,right_val]인 데이터 개수 반환
def count_by_range(arr,left_val,right_val):
  right_index = bisect_right(arr,right_val)
  left_index = bisect_left(arr,left_val)
  return right_index-left_index

n,x=map(int,input().split())
arr=list(map(int,input().split()))

#값이 [x,x]범위에 있는 데이터 개수 계산
count = count_by_range(arr,x,x)

if count==0: print(-1)
else: print(count)