[이분 탐색]

contents	datad
이분 탐색 알고리즘,  백준 1920번	2024.07.31

 

 

이분 탐색은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 

절반으로 줄여가며 찾는 탐색 방법  

 

범위를 절반으로 줄여나가는 건 이분 탐색의 탐색법입니다. 

선형 탐색은 O(N)에 동작하고 이분탐색은 O(lg N)에 동작하기 때문에 N이 커지면 커질수록 큰차이의 속도가 발생한다. 

 

 

이분 탐색의 구현 방법 

 

이분 탐색의 구현은 

1. 배열을 먼저 정렬을 시킨다. 

2. start와 end 변수를 적립해준다. 

    그래서 start는 맨 처음 end는 맨 뒤로 나누어 전체 범위를 나타내도록 한다..

3. 범위를 절반으로 줄이기 위해서 mid = (start+end)/2 지점으로 생각한다. 

 

4. mid와 찾고자 하는 값을 비교한 후  start 쪽인지 end 쪽인지  확인 하고 범위를 줄인다, 

5. mid+1를 start로 end를 end로 해서 다시 mid 값을 갱신 한 후 비교한다. 

이것을 값을 찾을 때 까지 반복한다. 

6. start와 end가 모이면 값이 없는 경우 이다. 

 

 

백준 1920번 

 

N = int(input())
A = list(map(int, input().split()))
M = int(input())
arr = list(map(int, input().split()))
A.sort()			# A 정렬

# arr의 각 원소별로 이분탐색
for num in arr:
    lt, rt = 0, N - 1		# lt는 맨 앞, rt는 맨 뒤
    isExist = False		# 찾음 여부

    # 이분탐색 시작
    while lt <= rt:		# lt가 rt보다 커지면 반복문 탈출
        mid = (lt + rt) // 2	# mid는 lt와 rt의 중간값
        if num == A[mid]:	# num(목표값)이 A[mid]값과 같다면 (목표값 존재여부를 알았다면)
            isExist = True	# isExist Ture 변경
            print(1)		# 1 출력
            break		# 반복문 탈출
        elif num > A[mid]:	# A[mid]가 num보다 작으면
            lt = mid + 1	# lt를 높임
        else:			# A[mid]가 num보다 크다면
            rt = mid - 1	# rt를 낮춤

    if not isExist:		# 찾지 못한 경우
        print(0)		# 0 출력