# 정렬되지 않은 자료의 검색 과정
# -첫 번쨰 원소부터 순서대로 검색대상과 키 값이 같은 원소가 있는지 비교
# -키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환
# -자료구조의 마지막에 갈 때까지 검색 대상을 찾지못하면 실패
#순차 검색 시간복잡도: O(N)
#ex
def sequentialSearch(a,n,key):
i =0
while i<n and a[i] != key:
i = i+1
if i<n: return i
else: return -1
# 정렬된 자료의 검색 과정
# 자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정
# 자료를 순차적으로 검색하면서 키 값을 비교함
# 원소의 키 값이 검색 대상의 키 값보다 크면 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료함.
#정렬되어있으므로, 검색 실패를 반환하는 경우 평균 비교회수가 반으로 줄어듦
# 시간복잡도는 여전히 O(N)
def sequentialSearch2(a,n,key):
i = 0
while(i<n and a[i] <key):
i = i+1
if i<n and a[i] ==key: return i
else: return -1
#이진 검색
# 자료의 가운데 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속하는 방법
# 검색범위를 반으로 줄여가면서 빠르게 검색을 수행함
# 이진 검색을 하기 위해서는 자료가 정렬된 상태여야함
# 정렬된 데이터 n개가 있는 경우의 시간복잡도는 순차 검색 시 o(n), 이진검색 시 o(logN)
#자료의 중앙에 있는 원소 선택
#중앙 원소의 값과 찾고자 하는 목표 값을 비교
# 목표값 < 중앙 원소값: 자료의 왼쪽 반에 대해 새로 검색을 수행
# 목표값 > 중앙 원소값 : 자료의 오른쪽 반에 대해 새로 검색을 수행
# 찾고자하는 값을 찾을 때까지 이를 반복
# 이진 검색은 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행함
# 이진검색의 경우 자료에 삽입이나 삭제가 발생하였을 떄 list의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요
def binarySearch(a,key):
start = 0
end = len(a)-1
while start<=end:
middle= start+ (end-start)//2
if key == a[middle]:
return True
elif key < a[middle]:
end = middle -1 #끌을 다시 새롭게 설정
else:
start = middle +1 # 시작점을 다시 새롭게 설정
return False
#재귀함수를 이용한 이진 검색 구현
def binarySearch2(a,low,high,key):
if low>high:
return False
else:
middle = (low+high)//2
if key == a[middle]:
return True
elif key < a[middle]:
return binarySearch2(a,low,middle-1,key)
elif a[middle]<key:
return binarySearch2(a,middle+1, high, key)
4839. [파이썬 S/W 문제해결 기본] 2일차 - 이진탐색 D2
T = int(input())
def binary(start,end,key,count):
middle = (start + end)//2
if middle == key:
return count
elif middle > key:
return binary(start,middle, key, count+1 )
else:
return binary(middle, end, key, count+1)
for test_case in range(1,T+1):
P,A,B = map(int,input().split())
count_A = binary(1,P,A,0)
count_B = binary(1,P,B,0)
if count_A < count_B:
print(f'#{test_case} A')
elif count_A > count_B:
print(f'#{test_case} B')
else:
print(f'#{test_case} 0')
어허히 이거 좀 헤맸는데
일단 a,b 다룰 때 같은 코드가 계속 반복되니 함수로 빼라는걸 인지하자구
책이 총 400쪽이면, 검색 구간의 왼쪽 l=1, 오른쪽 r=400이 되고, 중간 페이지 c= int((l+r)/2)로 계산
이 조건이 있어서 middle부터 범위를 다시 새로 잡아야함요