알고리즘

이분탐색을 응용한 알고리즘이므로 이분탐색을 먼저 공부하고 오자. Lower bound찾고자 하는 값 이상이 처음 나타나는 위치이다.Lower bound 과정Lower bound를 찾는 과정은 아래와 같다.1. 데이터셋의 중간 값을 가져온다.2. 중간 값과 찾고자 하는 값을 비교한다.    2-1. 중간 값이 찾고자 하는 값보다 작다면 left를 mid + 1로 변경한다.    2-2. 중간 값이 찾고자 하는 값보다 크거나 같다면 right를 mid로 변경한다.3. left 4. 반복이 끝나면 right가 Lower bound가 된다. 그림을 통해 살펴보자. 아래와 같은 데이터셋이 있고, target = 13라고 가정한다. 즉, 13보다 크거나 같은 값이 처음 나타나는 위치를 찾는다.모든 원소가 targe..

이분 탐색데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 범위를 절반씩 줄이면서 대상을 찾는다.시간 복잡도: $O(logN)$ 이분 탐색 과정이분 탐색을 위해서는 데이터셋이 정렬되어 있어야 한다. 데이터 셋은 아래와 같다. 찾고자 하는 데이터(target)는 100이라고 가정하고 설명한다.  1. 현재 데이터 셋의 중앙값을 선택한다. left는 데이터 셋의 시작 인덱스, right는 데이터 셋의 마지막 인덱스이다. 중앙값의 인덱스는 (left + right) / 2 를 통해 알아낸다.중앙값인 30은 우리가 찾고자하는 100보다 작다. 따라서 30보다 작은 index 중 100은 절대 존재할 수 없으므로 데이터셋의 길이를 줄여준다. 100의 ..