binary_search.hpp

Go to the documentation of this file.

#ifndef BINARY_SEARCH_HPP
#define BINARY_SEARCH_HPP

#include "space_settings.hpp"

// Binary search. Returns closest index of x0 that is less than x, i.e. i such that x0(i) <= x < x0(i+1)
// Returns -1 if x<x0(0) or x>=x0(n-1)
template<class Device>
KOKKOS_INLINE_FUNCTION int binary_search(const View<double*,CLayout,Device>& x0, const double x){
    const int& n = x0.extent(0);
    int low = 0;
    int high = n - 1;
    int mid;
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (x0(mid) <= x) {
            if (mid == n - 1 || x0(mid + 1) > x) {
                return mid; // Found the largest value <= xnew_i
            }
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // In case all elements in x0 are greater than xnew_i
}

#endif