4/14 이진 탐색(Binary Search)

이진 탐색이란 ?
오름차순으로 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘입니다.

배열 전체의 중간값을 target 값과 비교
중간값이 target 값보다 크면 왼쪽 부분만 선택
왼쪽부분의 중간값을 다시 target 과 비교
정방향으로 푸는 방법과 재귀로 푸는 방법 두 가지가 있습니다.
정방향도 어떻게 보면 개념적으로는 재귀로 푸는 방법과 같은 방법입니다.

이진 탐색 알고리즘의 장점

• 선형 탐색과 비교하여 탐색 시간이 빠르다. (이진 탐색의 시간 복잡도는 O(log N)입니다.)
  이진 탐색 알고리즘의 단점
• 정렬된 리스트에서만 사용될 수 있다.

문제 링크

수 찾기

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 200538 61043 40429 29.890%

문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1
1
1
0
0
1

import sys

for num in arr:
    lt, rt = 0, N - 1       #lt = 시작, rt = 끝
    isExit = False      #찾음

    while lt <= rt:     #lt가 rt보다 크거나 같으면 종료
        mid = (lt + rt) // 2        #시작 + 끝 // 2 하면 중간값
        if num == A[mid]:       #목표값이 중간값과 같으면
            isExit = True       #isExit를 True로 변경
            print(1)        #1 출력
            break       #반복문 탈출
        elif num > A[mid]:      #탐색값이 중간값보다 크면
            lt = mid + 1     #lt를 중간값 + 1 로 옮김
        else:                   #중간값이 탐색값보다 크면
            rt = mid - 1     #rt를 중간값 - 1 로 옮김

    if not isExit:      #찾지 못하면
        print(0)        #0을 출력