이진 탐색 알고리즘

풀어본 문제는 Baekjoon 의 1920번 이다.

 

 

처음에 풀었던 방식은 단순하게 N[0] 하고 M[0 - 4] 를 비교 N의 리스트의 값을 1개 씩 증가해가며 있으면 1 출력 없으면 0 출력 이런 식으로 풀었는데 시간 초과가 발생하였다...

 

그래서 값을 비교할 때 사용하는 알고리즘 중에 시간 복잡도 O(logn)인 이진 탐색 알고리즘을 사용하여 푼 문제이다.

 

이진 탐색은 정렬되어 있는 리스트에서 값을 비교할 때마다 찾는 값의 범위가 중간 값보다 작으면 왼쪽 크면 오른쪽을 대상으로 하여 찾는 알고리즘 이다.