이진탐색 Binary Search (c++,python)

이진탐색 Binary Search

● 탐색 전에 반드시 정렬되어 있어야 한다.

● 살펴보는 범위를 절반 씩 줄여가면서 답을 찾는다.

● 정렬 O(NlogN) + 이진탐색 O(logN) -> 결과적으로 O(NlogN)

● 미리 정렬되어 들어오면 이진탐색만 하면 되므로 O(logN)

● 한번만 탐색하는 경우,선형탐색 O(N) 이 더 빠를 수도 있다.

 

C++ lower_bound,upper_bound

● lower_bound: 찾으려는 key 값보다 같거나 큰 숫자가(x<=) 배열 몇 번째에서 처음 등장 하는지 찾기 위함. [A,B)

● upper_bound: 찾으려는 key 값을 초과(x<)하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함. (이 때, 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 한다.)

● 찾은 위치 값의 인덱스 반환

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {0, 1, 3, 3, 6, 6, 6, 7, 8, 8, 9};
    
    // 각 숫자가 몇 개인지 찾는 법
    int threeNum = upper_bound(v.begin(), v.end(), 3) - lower_bound(v.begin(), v.end(), 3);
    int fourNum = upper_bound(v.begin(), v.end(), 4) - lower_bound(v.begin(), v.end(), 4);
    int sixNum = upper_bound(v.begin(), v.end(), 6) - lower_bound(v.begin(), v.end(), 6);
    printf("number of 3: %d\n", threeNum); // 2
    printf("number of 4: %d\n", fourNum); // 0
    printf("number of 6: %d\n", sixNum); // 3
}

 

python bisect_left/right

from bisect import bisect_left, bisect_right

v = (0, 1, 3, 3, 6, 6, 6, 7, 8, 8, 9)

# 각 숫자가 몇개인지 찾는 법
threeNum = bisect_right(v,3) - bisect_left(v,3) # 4 - 2
fourNum = bisect_right(v,4) - bisect_left(v,4)
sixNum = bisect_right(v,6) - bisect_left(v,6)

print(f'number of 3: {three}') # 2
print(f'number of 4: {four}') # 0
print(f'number of 6: {six}') # 3