    01: #include <iostream>
    02: #include <vector>
    03: #include <cstdlib>
    04: #include <ctime>
    05:
    06: using namespace std;
    07:
    08: /**
    09:    Finds an element in a sorted vector.
    10:    @param v the sorted vector with the elements to search
    11:    @param from the start of the range to search
    12:    @param to the end of the range to search
    13:    @param a the value to search for
    14:    @return the index of the first match, or -1 if not found
    15: */
    16: int binary_search(vector<int> v, int from, int to, int a)
    17: {
    18:    if (from > to)
    19:       return -1;
    20:    int mid = (from + to) / 2;
    21:    int diff = v[mid] - a;
    22:    if (diff == 0) /* v[mid] == a */
    23:       return mid;
    24:    else if (diff < 0) /* v[mid] < a */
    25:       return binary_search(v, mid + 1, to, a);
    26:    else
    27:       return binary_search(v, from, mid - 1, a);
    28: }
    29:
    30: /**
    31:    Prints all elements in a vector
    32:    @param a the vector to print
    33: */
    34: void print(vector<int> a)
    35: {
    36:    for (int i = 0; i < a.size(); i++)
    37:       cout << a[i] << " ";
    38:    cout << "\n";
    39: }
    40:
    41: /**
    42:    Sets the seed of the random number generator.
    43: */
    44: void rand_seed()
    45: {
    46:    int seed = static_cast<int>(time(0));
    47:    srand(seed);
    48: }
    49:
    50: /**
    51:    Computes a random integer in a range.
    52:    @param a the bottom of the range
    53:    @param b the top of the range
    54:    @return a random integer x, a <= x and x <= b
    55: */
    56: int rand_int(int a, int b)
    57: {
    58:    return a + rand() % (b - a + 1);
    59: }
    60:
    61: int main()
    62: {
    63:    rand_seed();
    64:    vector<int> v(20);
    65:    v[0] = 1;
    66:    for (int i = 1; i < v.size(); i++)
    67:       v[i] = v[i - 1] + rand_int(1, 10);
    68:
    69:    print(v);
    70:    cout << "Enter number to search for: ";
    71:    int n;
    72:    cin >> n;
    73:    int j = binary_search(v, 0, v.size() - 1, n);
    74:    cout << "Found in position " << j << "\n";
    75:    return 0;
    76: }