For Programmer
7. 이진탐색 본문
728x90
이진탐색 알고리즘
소스코드
이진탐색 재귀적 구현
#이진 탐색 소스코드 구현(재귀함수)
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(찾고자 하는 값)을 입력 받기
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
#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)
파이썬 이진 탐색 라이브러리
이진탐색을 활용한 데이터 개수를 반환하는 함수 구현
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 = [1,2,3,3,3,3,4,4,8,9]
#값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))
#값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3))
2
6
728x90
'코팅테스트 > 코딩테스트 이론 정리' 카테고리의 다른 글
8-1. DP(다이나믹동적계획법) 개요 (0) | 2021.08.19 |
---|---|
7-2. 이진탐색 문제 (0) | 2021.08.18 |
6-2. 정렬 문제 (0) | 2021.08.18 |
6-1. 정렬(선택정렬,삽입정렬,퀵정렬,계수정렬) (0) | 2021.08.18 |
5-2. DFS&BFS 문제 (0) | 2021.08.14 |
Comments