#include <bits/stdc++.h>

using namespace std;

/**
 * Perform binary search on a sorted vector<int>.
 * @param vec    Sorted vector (ascending order).
 * @param target Value to locate.
 * @return Index of target in vec, or -1 if not found.
 */
int binarySearch(const vector<int> &array, int target) {
    int left = 0;
    int right = static_cast<int>(array.size()) - 1;

    while (left <= right) {
        // Prevent overflow for very large indices
        int mid = left + ((right - left) >> 1);
        int mid_val = array[mid];

        if (mid_val == target) {
            return mid; // Found
        } else if (mid_val < target) {
            left = mid + 1; // Search right half
        } else {
            right = mid - 1; // Search left half
        }
    }

    return -1; // Not found
}