이진탐색

what?

이진탐색이란 시작점, 중간점, 끝점 3개의 지점을 기준으로 탐색하는 것을 의미하고 중간점과 target(찾으려는 값)을 비교하며 탐색을 진행한다.

 

why?

탐색범위가 크거나 정렬이 된 배열속에서 특정 값을 빠르게 찾기 위해서 사용한다.

 

how?

시작점, 중간점, 끝점 3개를 설정하고 배열이 정렬되어있다는 가정하에 중간점과 target을 비교하며 탐색을 시작한다.

이때, target이 중간점의 원소보다 작다면 끝점은 중간점의 이전값이 되고 / 중간점의 원소보다 크다면 시작점이 중간점의 다음값이 된다.

이때, target이 중간점의 원소가 같을 때 target이 있던 위치는 중간점을 담은 변수의 값이 되고 탐색을 중단한다.

1. 재귀를 활용 2. while()문을 활용 = 반복문 활용

 

---

1. 재귀를 활용한 이진탐색 

#이진탐색 ->1. 재귀를 활용한 이진탐색
def binary_search(array, target, start, end):
    if start>end:
        return None
    mid = (start+end)//2 #몫 연산자를 사용해서 mid를 구하면 됨
    if array[mid] == target: #1. mid값이 곧 target일때
        return mid
    elif array[mid]>target:
        return binary_search(array, target, start, mid-1) #2. mid값보다 target이 작을 때
    else:
        return binary_search(array, target,mid+1, end) #3. mid값보다 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)

 

2. 반복문을 활용한 이진탐색

# 이진탐색 -> 반복문을 활용한 이진탐색

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 = 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)

---