이진 탐색

순차 탐색

#순차 탐색 소스코드 구현

def sequential_search(n, target, array):
# 각 원소 하나씩 확인하며
	for i in range(n):
    #현재의 원소가 찾고자 하는 원소와 동일한 경우
    	if array[i] == target:
        	return i+1 #현재의 위치 변환

print("생성할 원소 개수를 입력하고 한 칸 띄고 찾을 문자열을 입력하시오.")
input_data = input().split()
n = int(input_data[0]) #원소 개수
target = input_data[1]

print("앞서 적은 원소 개수만큼 문자열 입력하세요. 구분은 띄어쓰기로.")
array = input().split()

#순차 탐색 결과 출력
print(sequential_search(n,target,array))

재귀 함수로 구현한 이진 탐색

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. 부품 찾기

#입력받기 
n=int(input()) #가게의 부품 개수 입력
array=list(map(int,input().split())) #가게에 있는 전체 부품 번호 공백으로 구분해 입력
array.sort() #정렬 수행 **
m=int(input()) #손님이 확인 요청한 부품 개수 입력
x =list(map(int,input().split())) #손님이 확인 요청한 부품 번호 공백으로 구분해 입력

#손님이 확인 요청한 부품 번호 하나씩 확인
for i in x: #부품번호 돌면서 
  answer="no" #기본값으로 설정
  start=0 #시작점
  end=n-1 #끝점
  mid=(end+start)//2 #중간점 
  while start<=end:
    if array[mid]==i: #찾은 경우 
      answer="yes"
      break
    if array[mid]<i: #타겟값이 더 크다면  
      start=mid+1 # 시작점은 중간점의 오른쪽 값으로 갱신
    else: #타겟값이 더 작다면
      end=mid-1 #끝점은 중간점의 왼쪽 값으로 갱신
    mid=(start+end)//2 
  print(answer)

2. 떡볶이 떡 만들기

n, m=map(int, input().split())
array=list(map(int, input().split()))

#시작점, 끝점 설정
start=0
end=max(array)
mid=(start+end)//2

result=0
while start<=end:
  total=0
  for i in array:
    total+=max(0,i-mid)
# 떡의 양이 충분하면 덜 자르기 (오른쪽 탐색)  
   if total>=m:
     result=mid
     start=mid+1
#떡의 양이 부족하면 더 많이 자르기 (왼쪽 부분 탐색) 
   else:
    end=mid-1
   mid=(start+end)//2

print(result)

참조: https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체