이분탐색(이진탐색) - 탐색 시간복잡도 줄이기

알고리즘 문제를 풀다보면 시간 제한이 자주있다. for문 중복문만 쓰면 분명 시간초과 문제에 부딪히게 될 것이다🥲

이분탐색은 시간복잡도가 O(logN)으로, O(N) 보다 상대적으로 시간복잡도가 작다. 알고리즘 문제들이 보통 10,0000 입력 개수를 제한하는데, for문 중복을 쓴다면😨 시간초과해버린다.

그렇다면,, 시간복잡도 어떻게 줄일까? -> Binary Search 이분탐색을 활용해보자.

1. 이분탐색이란??

일단 이분탐색은 오름차순 또는 내림차순을 기준으로 정렬이 되어있다는 것이 전제로, 해당 수열에서 탐색하는 알고리즘이다.



이분탐색 개념

 

middle 인덱스를 찾고 해당 인덱스 위치에서 찾고자하는 수가 작으면 rt = mid - 1, 크다면 lt = mid + 1

이런식으로 반복을 한다. 반복문 종료 조건은 lt <= rt 이다. 이를 넘어서면 찾고자하는 수가 수열에 존재하지 않는다는 것!

파이썬 코드로 입력받은 m이 수열에서 몇 번째로 작은지 찾아보자.

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

lt = 0
rt = n - 1

while lt <= rt:
    mid = (lt + rt) // 2
    if arr[mid] == m:
        print(m + 1)
        break
    elif arr[mid] < m:
        lt = mid + 1
    else:
        rt = mid - 1

# 전제조건 : 이분탐색 O(logN) 을 위해서는 오름차순 또는 내림차순으로 정렬이 되어있어야함.
# 참고로 파이썬 내장함수 sort()는 nlogn 시간복잡도를 가지고 있다. 밑은 2임.