[파이썬] 백준 13706 이분탐색이란

백준 13706 문제풀이

https://www.acmicpc.net/problem/13706

백준 13706

이분탐색의 기본 원리

1. 전체 배열 중에 중간을 찾고,
2. 찾으려는 값이 중간 값보다 작으면, 중간에서 왼쪽으로 찾는다.
   배열의 end 값 변경
3. 찾으려는 값이 중간 값보다 크면, 중간에서 오른쪽으로 찾는다.
   배열의 start 값 변경
4. 위 1번에서 3번을 반복하여 값을 찾는다.

이분탐색 전제조건

전체 배열은 정렬되어 있다는 전제하에 진행한다.

 

이분탐색 기본 알고리즘 코드

반복문과 재귀호출 방법이 있다.

기본 알고리즘 코드를 숙지하고, 이후 상황에 맞게 적절히 수정하여 사용

 

▶ 반복문

#이분탐색 반복문
def binary_search(target, data):
    data.sort() #data 정렬 먼저
    start = 0 	#배열의 맨 처음 위치
    end = len(data) - 1 	# 배열의 마지막 위치

    while True:
        if start > end:
            break; # target 값 없음
        # 중간값 위치
        mid = (start + end) // 2				
        # target 값 찾음. 위치 반환
        if data[mid] == target:
            return mid 		
	    # target 값이 작으면 왼쪽 탐색. end 변경
        elif data[mid] > target: 
            end = mid - 1
        # target 값이 크면 오른쪽 탐색. start 변경
        else:
            start = mid + 1
    return

 

▶ 재귀 호출

#이분탐색 재귀
def binary_search(target, start, end):
    if start > end:	    # 범위를 넘어도 못찾는다면 -1 반환
        return -1
    mid = (start + end) // 2  # 중간값 위치

    if data[mid] == target:   # target 값 찾음. mid 위치 반환
        return mid 
    # target 값이 작으면 왼쪽 탐색. end 변경
    elif data[mid] > target:
        end = mid - 1
    # target 값이 크면 오른쪽 탐색. start 변경
    else:
        start = mid + 1
    # 줄어든 범위를 더 탐색
    return binary_search(target, start, end)

def call_search(target, data):
    data.sort()  #data 정렬 먼저
    start = 0    #배열의 맨 처음 위치
    end = len(data) - 1  # 배열의 마지막 위치
    return binary_search(target, start, end) #이분탐색 호출

 

풀이

이분탐색으로 양의 정수 N 제곱근 탐색

import sys
#양의 정수 N이 주어진다
N = int(sys.stdin.readline().rstrip())
start = 0
end = N
#이분탐색 로직으로 정수 N의 제곱근 찾는다.
while True:
    #범위를 벗어나면 빠져나감
    if start > end:
        break
    #중간값 계산
    mid = (start + end) // 2    
    #제곱근이 N 보다 작으면 오른쪽 탐색
    if mid ** 2 < N:
        start = mid + 1
    #제곱근이 N 보다 크면 왼쪽 탐색
    else:
        end = mid - 1
print(start)
"""
36
6
"""