Binary search implemented by C++.

binary_search.cpp

/*
 * @author  duruyao
 * @file    binary_search.cpp
 * @desc    
 * @date    2021-10-07
 * @version 1.0
 */

#include <vector>
#include <iostream>

/**
 * binarySearch searchs the target element by binary search algorithm.
 *
 * ---time complexity---
 *
 * best    case:    O(1)
 * average case:    O(log n)
 * worst   case:    O(log n)
 *
 * ---when to use---
 *
 * (1) data set is ordered AND
 * (2) data set can be accessed through index.
 *
 * @tparam T        is a certain data type
 * @param input     is an ordered data set to be searched
 * @param begin     is the first index
 * @param end       is the index past the last index
 * @param cmpFunc   is a function for comparing elements of data set
 * @param target    is a element to be found
 * @return          index of target if searching successfully, otherwise return -1
 */
template<typename T>
int binarySearch(std::vector<T> &input, int begin, int end, int (*cmpFunc)(const T &, const T &), const T &target) {
    if (end - begin == 1) {
        return (cmpFunc(target, input[begin]) == 0) ? begin : -1;
    }
    auto medIdx = (begin + end - 1) / 2;
    if (cmpFunc(target, input[medIdx]) < 0) {
        return binarySearch(input, begin, medIdx, cmpFunc, target);
    } else if (cmpFunc(target, input[medIdx]) > 0) {
        return binarySearch(input, medIdx + 1, end, cmpFunc, target);
    }
    return medIdx;
}

int cmpInt(const int &n1, const int &n2) {
    return n1 - n2;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &input) {
    for (auto &it : input) { os << it << " "; }
    return os;
}

int main(int argc, char **argv) {
    std::vector<int> array{2, 11, 11, 15, 21, 22, 23, 26, 26, 27, 29, 29, 30, 35, 35, 36, 40, 42, 49, 56,
                           58, 59, 62, 62, 63, 67, 67, 67, 68, 69, 72, 77, 82, 83, 86, 86, 90, 92, 93, 93};
    std::cout << array << std::endl;
    auto target = 49;
    auto idx = binarySearch(array, 0, (int) array.size(), cmpInt, target);
    std::cout << target << " is array[" << idx << "]" << std::endl;
    return 0;
}