Binary Search

search index of item exactly equal to given number (if repeated, then first occurrence)

// **************** Own Implementation ****************

int binarySearch(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        if(arr[low] == target){
            return low;
        } else {
            return -1;
        }
    } 

    int mid = (low + high) / 2;

    if (arr[mid] < target) {
        return binarySearch(arr, mid + 1, high, target);
    } else {
        return binarySearch(arr, low, mid, target);
    }
}


int binarySearch(vector<int>& arr, int target) {
    if (arr.empty()) {
        return -1;
    }
    return binarySearch(arr, 0, arr.size() - 1, target);
}





// ******************** Using STL **********************
#include <algorithm>

int binarySearch(vector<int>& arr, int target) {
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end() && *it == target) {
        return it - arr.begin();
    }
    return -1;
}

search index of item exactly equal to given number (if repeated, then last occurrence)

// **************** Own Implementation ****************

int binarySearch(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        if(arr[low] == target){
            return low;
        } else {
            return -1;
        }
    } 

    int mid = (low + high + 1) / 2;

    if (target < arr[mid]) {
        return binarySearch(arr, low, mid-1, target);
    } else {
        return binarySearch(arr, mid, high, target);
    }
}


int binarySearch(vector<int>& arr, int target) {
    if (arr.empty()) {
        return -1;
    }
    return binarySearch(arr, 0, arr.size() - 1, target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearch(vector<int>& arr, int target) {
    // upper_bound returns an iterator to the first element
    // that is strictly greater than 'target'
    auto it = upper_bound(arr.begin(), arr.end(), target);

    if(it == arr.begin()){
        // the first element is strictly greater than 'target'
        return -1;
    }

    // Go one step back
    it--;

    if (*it == target) {
        return it - arr.begin();
    } else {
        return -1;
    }
}

search index of item exactly equal to given number (if repeated, then any occurrence)

// **************** Own Implementation ****************


int binarySearch(vector<int>& arr, int low, int high, int target) {
    if (low > high) {
        return -1;
    }

    int mid = (low + high) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearch(arr, mid + 1, high, target);
    } else {
        return binarySearch(arr, low, mid - 1, target);
    }
}


int binarySearch(vector<int>& arr, int target) {
    if (arr.empty()) {
        return -1;
    }
    return binarySearch(arr, 0, arr.size() - 1, target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearch(vector<int>& arr, int target) {
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end() && *it == target) {
        return it - arr.begin();
    }
    return -1;
}

search index of first item just greater_than_or_equal to given number

// **************** Own Implementation ****************

int binarySearchGte(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        return low;
    }

    int mid = low + (high - low) / 2;

    if (target <= arr[mid]) {
        return binarySearchGte(arr, low, mid, target);
    } else {
        return binarySearchGte(arr, mid + 1, high, target);
    }
}

int binarySearchGte(vector<int>& arr, int target) {
    // assuming arr[N] contains infinity, answer is going be one of [0,N]
    return binarySearchGte(arr, 0, arr.size(), target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearchGte(vector<int>& arr, int target) {
    auto it = lower_bound(arr.begin(), arr.end(), target);
    
    if (it == arr.end()) {
       // return arr.size() if no such element is found
       // or -1 if you prefer to indicate 'not found'.
       return arr.size();
    }
 
    return it - arr.begin();
}

search index of first item strictly_greater_than given number

// **************** Own Implementation ****************

int binarySearchGreater(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        return low;
    }

    int mid = low + (high - low) / 2;

    if (target < arr[mid]) {
        return binarySearchGreater(arr, low, mid, target);
    } else {
       return binarySearchGreater(arr, mid + 1, high, target);
    }
}

int binarySearchGreater(vector<int>& arr, int target) {
    // assuming arr[N] contains infinity, answer is going be one of [0,N]
    return binarySearchGreater(arr, 0, arr.size(), target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearchGreater(vector<int>& arr, int target) {
    auto it = upper_bound(arr.begin(), arr.end(), target);
    return it - arr.begin();
}

search index of last item which is less_than_or_equal to given number

// **************** Own Implementation ****************

int binarySearchLte(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        return low;
    }

    int mid = (low + high + 1) / 2;

    if (arr[mid] <= target) {
        return binarySearchLte(arr, mid, high, target);
    } else {
        return binarySearchLte(arr, low, mid-1, target);
    }
}

int binarySearchLte(vector<int>& arr, int target) {
    // assuming arr[-1] contains -infinity, answer is going be one of [-1,N-1]
    return binarySearchLte(arr, -1, arr.size()-1, target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearchLte(vector<int>& arr, int target) {
    // Find the first element strictly greater than 'target'.
    auto it = upper_bound(arr.begin(), arr.end(), target);

    // If 'it' is at the beginning, it means all elements in the vector
    // are strictly greater than 'target'
    if (it == arr.begin()) {
        return -1; // No element <= target found.
    }

    // If 'it' is not at the beginning, then the element immediately before it
    // is the last element less than or equal to 'target'.
    it--;
    return it - arr.begin();
}

search index of last item which is strictly_lesser_than given number

// **************** Own Implementation ****************

int binarySearchLesser(vector<int>& arr, int low, int high, int target) {
    if (low == high) {
        return low;
    }

    int mid = (low + high + 1) / 2;

    if (arr[mid] < target) {
        return binarySearchLesser(arr, mid, high, target);
    } else {
        return binarySearchLesser(arr, low, mid-1, target);
    }
}

int binarySearchLesser(vector<int>& arr, int target) {
    // assuming arr[-1] contains -infinity, answer is going be one of [-1,N-1]
    return binarySearchLesser(arr, -1, arr.size()-1, target);
}



// ******************** Using STL **********************
#include <algorithm>

int binarySearchLesser(vector<int>& arr, int target) {
    // lower_bound finds the first element >= target.
    auto it = lower_bound(arr.begin(), arr.end(), target);

    // If 'it' is the beginning of the array, it means all elements are >= target,
    // or the array is empty
    if (it == arr.begin()) {
        return -1; // No element is strictly less than the target
    }

    // Decrement the iterator to point to the element immediately before
    // the first element greater than or equal to 'target'. This will be the
    // last element strictly less than 'target'.
    it--;

    return it - arr.begin();
}