binary_search #5
Description
binary_search
-
Binary search 사용할 때, 데이터는 정렬되어 있어야함.
-
선형 탐색은 O(N)에 동작하고 이분 탐색은 O(log N)에 동작한다. 따라서 N이 커질 수 록 속도 차이 커짐
( N개로 이루어진 정수 배열에서 M 개의 key 찾기)
- 만약 M개의 수에 대해 선형 탐색한다면 ? 시간 복잡도 = O(MN)
- 만약 배열을 정렬하고 이분 탐색 수행한다면? 시간 복잡도 = O(NlogN + MlogN)
(NlogN => 정렬에 필요, MlogN => 이분 탐색에 필요)
a[i] + a[j] + a[k] = a[l]
- 뭔가 2개를 묶거나 한 다음, 어느 한쪽의 값을 이분 탐색으로 찾아서 시간복잡도를 낮추는 아이디어는 이분 탐색 관련 응용문제에서 핵심적으로 많이 사용됨.
- a[i] + a[j] + a[k] = a[l] 는 a[i] + a[j] = a[l] - a[k] 이다. 따라서 a[i] + a[j]를 two[m]으로 만들어서, two[m] = a[l] - a[k] 로 구현 가능
- 이때, a[l] - a[k] 값이 two 배열 내에 있는지 이분 탐색으로 search하면 됨.