낙서 코딩

개념

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

https://blog.hexabrain.net/246 참고

조건

• 수들이 오름차순 또는 내림차순으로 정렬 되어 있어야 한다.
• 원하는 값을 찾으면 종료한다. (종료 조건1) → 값을 찾음
• 왼쪽값이 오른쪽 값보다 커지면 종료한다. (종료조건2) → 값이 없음

사용 하면 좋은 경우

1. 리스트에서 값을 찾을 때 시간을 단축해야 하는 경우
   • list에서 find() 함수를 사용하거나 반목문으로 값을 찾을 시 O(N)의 시간이 필요하기 때문에 이진 탐색을 사용하면 시간 효율성을 증가 시킨다.
2. 조건에 맞는 최소 또는 최대값을 찾아야 하는 경우
   • 이러한 경우에는 index를 left, right로 두지 않고 left = 가장 작은 값, right = 가장 큰 값 으로 설정하여 배열에서의 위치가 아닌 조건에 맞는 값을 구 할 수 있도록 한다.

구현 방법

기본 이진 탐색

1. 반복문

#include <iostream>
#include <vector>

using namespace std;

int BinarySearch(vector<int> num, int target) {
    int left = 0, right =(int) num.size(), mid = 0;
    sort(num.begin(), num.end()); //숫자 오름차순 정렬
    //num : {1, 2, 4, 5, 15, 56, 123, 125, 199, 3215}
    while(left <= right) { //종료 조건
        mid = (left + right) / 2;
        if(num[mid] == target) {// target을 찾았을 때
            return mid;
        }
        else if(num[mid] > target) { //target보다 클 때 -> 왼쪽 수들을 확인
            right = mid - 1;
        }
        else { //target보다 작을 때 -> 오른쪽 수들을 확인
            left = mid + 1;
        }
    }
    return -1;
}

1. 재귀 함수

#include <iostream>
#include <vector>

using namespace std;
//재귀 함수는 num을 정렬 해서 함수 호출
int RecurBinarySearch(vector<int> num, int target, int left, int right) {
    if(left > right) return -1; //종료 조건
    int mid = (left + right) / 2;
    if(num[mid] == target) { //target을 찾았을 때
        return mid;
    }
    else if(num[mid] > target) { // target보다 클 때
        return RecurBinarySearch(num, target, left, mid-1);
    }
    else { //target보다 작을 때
        return RecurBinarySearch(num, target, mid+1, right);
    }
}

int main(int argc, const char * argv[]) {
    vector<int> num {1,5,2,199,56,3215,125,123,15,4};
    sort(num.begin(), num.end());
    int left = 0, right = (int)num.size();
    cout << RecurBinarySearch(num, 199, left, right) << endl;
    return 0;
}

UpperBound

목표값보다 큰 값이 처음 발견되는 곳 찾기

int UpperBound(vector<int> num, int target) {
    int left = 0, right = (int) num.size(), mid = 0;
    sort(num.begin(), num.end());
    int ans = 0;
    while(left <= right) {
        mid = (left + right) / 2;
        if(num[mid] <= target) { // 목표보다 작거나 같으면 오른쪽 보기
            left = mid + 1;
        }
        else { // 목표보다 크면 답의 후보로 두고 왼쪽 보기
            ans = mid;
            right = mid - 1;
        }
    }
    return ans;
}

LowerBound

목표값보다 작은 값이 처음 발견되는 곳 찾기

int LowerBound(vector<int> num, int target) {
    int left = 0, right = (int) num.size(), mid = 0;
    sort(num.begin(), num.end());
    int ans = 0;
    while(left <= right) {
        mid = (left + right) / 2;
        if(num[mid] >= target) { //목표보다 크거나 같으면 왼쪽 보기
            right = mid - 1;
        }
        else { // 목표보다 작으면 답의 후보로 두고 오른 쪽 보기
            ans = mid;
            left = mid + 1;
        }
    }
    return ans;
}

결과

int main(int argc, const char * argv[]) {
    vector<int> num {1,5,2,199,56,3215,125,123,15,4};
    sort(num.begin(), num.end());
    int left = 0, right = (int)num.size();
    for(int i = 0; i < num.size(); i++) {
        cout << num[i] << " ";
    }
    cout << endl;
    cout << "재귀 : " << RecurBinarySearch(num, 199, left, right) << endl;
    cout << "반복문 : " << BinarySearch(num, 199) << endl;
    cout << "UpperBound : " << UpperBound(num, 199) << endl;
    cout << "LowerBound : " << LowerBound(num, 199) << endl;
    return 0;
}

시간 복잡도

• O(logN)