Binary Search

Custom lower_bound Implementation

The goal of lower_bound is to find the first position in a sorted array where the value is not less than a target value.

Code

int customLowerBound(const vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) 
            left = mid + 1;
        else 
            right = mid;
    }
    return left; // Returns the index where target could be inserted
}

int main() {
    vector<int> arr = {1, 2, 4, 4, 5, 7, 9};
    int target = 4;
    int lb = customLowerBound(arr, target);
    cout << "Custom lower_bound of " << target << ": index " << lb << endl;
    return 0;
}

Custom upper_bound Implementation

The goal of upper_bound is to find the first position in a sorted array where the value is greater than a target value.

Code

int customUpperBound(const vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) 
            left = mid + 1;
        else 
            right = mid;
    }
    return left; // Returns the index where elements are strictly greater than target
}

int main() {
    vector<int> arr = {1, 2, 4, 4, 5, 7, 9};
    int target = 4;
    int ub = customUpperBound(arr, target);
    cout << "Custom upper_bound of " << target << ": index " << ub << endl;
    return 0;
}

Summary

Function	What it Finds	Example Output
lower_bound	First position where value >= target	4 at index 2
upper_bound	First position where value > target	5 at index 4