구간 길이 구하기

배열내에 임의의 숫자들이 정렬되어 저장되있다.

또한 임의의 수가 2개 주어진다 할때

배열내에서 2개의 수 사이에 있는 성분들의 갯수는 몇개일까?

 

이것 문제를 해결하기 위한 이상적인 방법은 이진탐색을 이용하는 것이다.

 

2개의 임의의 수 중에 작은수를 기준으로 lower_bound, 큰수를 기준으로 upper_bound를 해서 나온 2개 요소의 위치를 빼주면 구간길이를 구할 수 있다.

 

// Example program
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main()
{
    vector<int> vi;
    
    for(int i=0; i<10; i++)
        vi.push_back(i * 10);    
    
    vector<int>::iterator from, to;    
    
    from = lower_bound(vi.begin(), vi.end(), 28);
    to = upper_bound(vi.begin(), vi.end(), 72);
    
    cout << to - from << endl;
    
    return 0;
}
 

28을 기준으로 lower_bound를 하면 30을 찾고, 72를 기준으로 upper_bound를 하면 80을 찾게된다.

각각의 index는 3과 8이 되며 $8-3=5$ 인데 이는 28과 72 사이에 있는 배열 요소들의 갯수와 동일하다(30, 40, 50, 60, 70)

 

그리고 lower_bound에 20을, upper_bound에 80을 넣으면 각각 20과 90의 반복자를 얻게된다. 각각 요소들의 벡터내 첨자는 2와 9 인데 $9-2=7$ 이 나오며 이는 20과 80사이의 요소들의 갯수와 동일하다(20, 30, 40, 50, 60, 70, 80)

 

이진탐색은 숫자 뿐만 아니라 문자 및 문자열의 검색에도 사용될 수 있으므로 이러한 개념을 잘 숙지해놓으면 유용할것이라 생각된다.