이진 탐색 | Binary Search

 

이진 탐색 | Binary Search

 

 

이진 탐색이란 정렬된 배열에서 특정한 타겟값을 찾는 검색 알고리즘이다.

 

이진 탐색의 시간 복잡도는 O(logN)으로 순차 탐색의 시간 복잡도O(N)에 비해 상대적으로 빠른 탐색 알고리즘이다.

 

그래서 주어진 배열의 크기가 매우 크거나 효율성을 높이고 싶다하면 이진탐색 알고리즘을 가져다가 쓰면 좋다. 백준 부술때 n이 어지러울 정도로 큰 수로 주어지면 이건 이진탐색이구나 하고 시작하면 반은 성공한다👊

 

 

이진 탐색의 특징

이진 탐색은 배열 안의 데이터가 정렬되어 있어야만 사용할 수 있으며, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.

 

이진 탐색은 위치를 나타내는 변수 3개를 사용한다. ➡️ 탐색 범위의 시작점, 끝점, 중간점

 

다음 세개의 변수를 바탕으로 찾으려는 데이터와 중간점 위치의 데이털르 반복적으로 비교해 나가면서 타겟값을 찾아나간다.

 

말로 풀어쓰면 감이 안온다. 같이 예시를 보면서 이진 탐색을 살펴보자

 

 

---

 

예시

다음은 백준의 수 찾기 문제이다.

1920번: 수 찾기

 

문제 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을 출력한다

 

n = int(input())
num = list(map(int, input().split()))

m = int(input())
arr = list(map(int, input().split()))

for i in arr:
    if i in num:
        print(1)
    else:
        print(0)

 

매우 간단한 문제이다. 근데 이렇게 풀면 시간 초과가 뜬다.  m번의 탐색을 n번 진행해야 하는 데 문제에서 주어졌듯이 m과 n은 최대 100,000개이다. 벌써 어지럽다 이러면 뭐다? 이진 탐색이다.

 

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
check = list(map(int, input().split()))

arr.sort()


def find(num):
    left, right = 0, n-1
    while left <= right:
        mid = (left+right) // 2
        if num == arr[mid]:
            return True
        if arr[mid] < num:
            left = mid + 1
        else:
            right = mid - 1
    return False


for i in check:
    print(1) if find(i) else print(0)

 

이진 탐색의 뽀인트는 탐색 구간 설정이다.

중간값이 타겟값보다 작다? 그러면 시작점을 mid + 1로 올려주고

중간값이 타겟값보다 크다? 그러면 끝점을 mid - 1로 내려주면 되는 거다.

 

 

또 한 번 성장해 버렸다