[03. 검색 알고리즘] 보초법(Sentinel Method)

#include <iostream>
using namespace std;

// 조건 check 2개 (i < N, arr[i] == key)
int search1(const int arr[], int N, int key) {
    for (int i = 0; i < N; i++)
        if (arr[i] == key)
            return i;
    return -1;
}

// 보초법: 조건 check 1개 (arr[i] == key)
int search2(int arr[], int N, int key) {
    arr[N] = key;
    for (int i = 0; ; i++)
        if (arr[i] == key)
            return i==N ? -1 : i;
}

int main(int num) {
    const int N = RAND_MAX;
    int arr[N+1];					// 보초법: 여유공간 1개 확보
    for (int i = 0; i < N; ++i)
        arr[i] = rand();
    
    //cout << search1(arr, N, 3);
    cout << search2(arr, N, 3);
}