Binary search is an efficient algorithm for locating a target value within a sorted sequence. The standard implementation returns the position of any matching element, but may not identify the first occurence when duplicates exist.

int binarySearch(int left, int right, int target) {
    int result = -1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (data[middle] == target) {
            result = middle;
            right = middle - 1; // Continue searching left for first occurrence
        } else if (data[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return result;
}

This modified version continues searching leftward after finding a match to ensure the first occurrence is returned.

C++ provides built-in functions for binary search operations through the <algorithm> header. The lower_bound function returns an iterator to the first element that is not less than the target value.

#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> numbers = {1, 3, 3, 3, 5, 7, 9, 11, 13, 15, 15};
    int target = 3;
    
    auto position = lower_bound(numbers.begin(), numbers.end(), target);
    int index = position - numbers.begin();
    
    if (position != numbers.end() && *position == target) {
        cout << "First occurrence at index: " << index << endl;
    } else {
        cout << "Target not found" << endl;
    }
    
    return 0;
}

When the target value exists in the collection, lower_bound returns an iterater to the first occurrence. If the target is not found, it returns an iterator to the first element greater than the target, or end() if no such element exists.

The upper_bound function complements lower_bound by returning an iterator to the first element strictly greater than the target value. Together, these functions can idenitfy all occurrences of a value in a sorted range.

vector<int> data = {2, 4, 4, 4, 6, 8};
int value = 4;

auto lower = lower_bound(data.begin(), data.end(), value);
auto upper = upper_bound(data.begin(), data.end(), value);

// The range [lower, upper) contains all occurrences of value
int count = upper - lower; // Returns 3 for this example