24.08.14 알고리즘 - 이진 탐색(Binary search)

 

이진 탐색(Binary search)

---

이진 탐색은 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다.

 

시간 복잡도 : O(logN)

 

1. 배열을 오름차순으로 정렬한다.

2. 배열의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.

3. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다.

    ⓐ target이 mid 값보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)

    ⓑ target이 mid 값보다 크면 start를 mid 오른쪽 값으로 바꿔준다. (절반의 오른쪽 탐색)

 

def binary_search(target, array):
    array.sort()
    start = 0 				# 맨 처음 위치
    end = len(array) - 1 	# 맨 마지막 위치
    
    while start <= end:
    	mid = (start + end ) // 2	# 중간 값
        
        if array[mid] == target:
        	return mid				# target 위치 반환
        elif array[mid] > target:   # target이 작으면 왼쪽 탐색
        	mid = end - 1
        else:						# target이 크면 오른쪽 탐색
        	start = mid + 1
    return

 

---

백준 1920_ 수찾기

 

1. 이진탐색

N = int(input())
A = list(map(int,input().split()))
M = int(input())
B = list(map(int,input().split()))

A.sort()

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return True
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return False

for b in B:
    if binary_search(b, A):
        print(1)
    else:
        print(0)

 

2. set으로 탐색

N = int(input())
A = set(map(int,input().split()))
M = int(input())
B = map(int,input().split())

for b in B:
    print(1) if b in A else print(0)

 

 

백준 10815_숫자카드

N = int(input())
array1 = list(map(int,input().split()))
M = int(input())
array2 = list(map(int,input().split()))

array1.sort()

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) //2

        if target == data[mid]:
            return True
        elif target > data[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return False

for i in array2:
    print(1, end=" ") if binary_search(i,array1) else print(0, end=" ")