[알고리즘] 이진 탐색

이진 탐색 두 가지 유형
1. 임의의 값 x의 인덱스를 찾는 것
2. 특정한 조건을 만족하는 최적해의 인덱스를 찾는 것

코드

크기 1000의 배열에 0이상 1000미만인 정수를 랜덤으로 넣고 오름차순으로 정렬한 후 x=723 인 인덱스와 x*x<250000인 인덱스의 최댓값을 찾는 코드

#include <iostream>
#include <ctime>
#include <algorithm>
using namespace std;
const int LOW_BOUND = 0;
const int HIGH_BOUND = 999;
int arr[1000];

// x값의 인덱스를 찾는 이진 탐색
int BS_value(int x) {
    int lo = LOW_BOUND;
    int hi = HIGH_BOUND;
    int mid;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] < x)
            lo = mid + 1;
        else if (arr[mid] > x)
            hi = mid - 1;
    }
    return -1;
}

// 최적해의 기준 함수
bool Judge(int x) {
    return x * x < 250000;
}

// Judge가 true인 인덱스의 최대값을 찾는 이진 탐색
int BS_optimum() {
    // Judge(LOW_BOUND)는 true여야 함
    if (!Judge(LOW_BOUND))
        return -1;
    int lo = LOW_BOUND;
    int hi = HIGH_BOUND;
    int mid;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (Judge(arr[mid]))
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return hi;
}

int main(void) {
    srand(time(NULL));
    for (int i = 0; i < 1000; ++i)
        arr[i] = rand() % 1000;
    sort(arr, arr + 1000);

    int x = 723;

    if (BS_value(x) != -1)
        cout << "x index : " << BS_value(x) << '\n';
    else
        cout << "No Index\n";

    if (BS_optimum() != -1)
        cout << "Maximum Index Satisfying Judge : " << BS_optimum() << '\n';
    else
        cout << "No Index\n";

    return 0;
}