중복 여부에 따른 이진탐색(Binary Search)

알고리즘 문제를 해결하다보니 이진탐색을 경우에 맞게 변경해야 하는 경우가 생겼다.

 

정렬된 배열에서 중앙값(median)을 비교하여 검색범위를 절반으로 줄여나가는 방식이다. 

 

따라서 이진탐색은 O(log N)의 성능을 갖는다.

 

 

중복이 있는 배열에서 성분 중 가장 앞의 위치를 찾는 법

 1. 값 중복 O
 2. target이 모든 v에 대해 더 작은 경우 : 0
 3. target이 모든 v에 대해 더 큰 경우 : v.size()
 4. target이 v안에 없는 경우 : target보다 큰 가장 가까운 v의 인덱스 return
 5. 중복된 값이 있는 경우 : 같은 값 중 가장 작은 인덱스 return

int solution(vector<int> v, int target) {
    int start = 0;
    int end = v.size() - 1;
    int mid;
    while (start <= end) {
        mid = (start + end) / 2;
        if (v[mid] < target) {
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
 
    return start;
}

v = {3, 5, 5, 5, 10} input(1) // 0 input(3) // 0 input(4) // 1 input(5) // 1 input(7) // 4 input(10) // 4 input(15) // 5

cs

중복이 있는 배열에서 성분 중 가장 뒤의 위치를 찾는 법

 1. 값 중복 O
 2. target이 모든 v에 대해 더 작은 경우 : -1
 3. target이 모든 v에 대해 더 큰 경우 : v.size() - 1
 4. target이 v안에 없는 경우 : target보다 작은 가장 가까운 v의 인덱스 return
 5. 중복된 값이 있는 경우 : 같은 값 중 가장 큰 인덱스 return

int solution(vector<int> v, int target) {
    int start = 0;
    int end = v.size() - 1;
    int mid;
    while (start <= end) {
        mid = (start + end) / 2;
        if (v[mid] <= target) {
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
 
    return end;
}

v = {3, 5, 5, 5, 10} input(1) // -1 input(3) // 0 input(4) // 0 input(5) // 3 input(7) // 3 input(10) // 4 input(15) // 4

cs

중복이 없는 배열에서 target보다 크거나 같은 성분 찾는 법

 1. 값 중복 X
 2. target이 모든 v에 대해 더 작은 경우 : 0
 3. target이 모든 v에 대해 더 큰 경우 : v.size()
 4. target이 v안에 없는 경우 : target보다 큰 가장 가까운 v의 인덱스 return

int solution(vector<int> v, int target) {
    int start = 0;
    int end = v.size() - 1;
    int mid;
    while (start <= end) {
        mid = (start + end) / 2;
        if (v[mid] > target) {
            end = mid - 1;
        }
        else if (v[mid] < target) {
            start = mid + 1;
        }
        else return mid;
    }
    
    return start;
}

v = {1, 3, 5, 7, 9} input(0) // 0 input(4) // 2 input(5) // 2 input(6) // 3 input(10) // 5

cs

중복이 없는 배열에서 target보다 작거나 같은 성분 찾는 법

 1. 값 중복 X 
 2. target이 모든 v에 대해 더 작은 경우 : 0 
 3. target이 모든 v에 대해 더 큰 경우 : v.size() 
 4. target이 v안에 없는 경우 : target보다 큰 가장 가까운 v의 인덱스 return

int solution(vector<int> v, int target) {
    int start = 0;
    int end = v.size() - 1;
    int mid;
    while (start <= end) {
        mid = (start + end) / 2;
        if (v[mid] > target) {
            end = mid - 1;
        }
        else if (v[mid] < target) {
            start = mid + 1;
        }
        else return mid;
    }
 
    return end;
}

v = {1, 3, 5, 7, 9} input(0) // -1 input(4) // 1 input(5) // 2 input(6) // 2 input(10) // 4

cs

 

샘플코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> v, int target);
 
int main() {
    vector<int> vec;
 
    vec.push_back(3);
    vec.push_back(5);
    vec.push_back(5);
    vec.push_back(5);
    vec.push_back(10);
    
    /*vec.push_back(1);
    vec.push_back(3);
    vec.push_back(5);
    vec.push_back(7);
    vec.push_back(9);*/
 
    sort(vec.begin(), vec.end());
 
    int temp;
    do {
        cin >> temp;
        cout << solution(vec, temp) << endl;
    } while (temp >= 0);
    
}
 
// solutoin() 원형