binsearch.h

Go to the documentation of this file.

/*
 * Copyright (c) 2014-2015, NVIDIA CORPORATION
 * Copyright (c) 2015, Nuno Subtil <subtil@gmail.com>
 * Copyright (c) 2015, Roche Molecular Systems Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *    * Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *    * Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *    * Neither the name of the copyright holders nor the names of its
 *      contributors may be used to endorse or promote products derived from
 *      this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#pragma once

#include "../types.h"

namespace lift {

// perform a binary search on a sorted array
// returns the index of any element in the array that is equal to val, or -1 if not found
template <typename T>
CUDA_HOST_DEVICE uint32 binary_search(const T *data, uint32 size, const T val)
{
    uint32 first = 0;
    uint32 last = size;

    while(last - first > 0)
    {
        uint32 i = first + ((last - first) / 2);

        if (data[i] == val)
            return i;

        if (data[i] < val)
        {
            if (i == first)
            {
                first++;
            } else {
                first = i;
            }
        } else {
            if (i == last)
            {
                last--;
            } else {
                last = i;
            }
        }
    }

    return uint32(-1);
}

// perform a binary search on a sorted array
// return the index of the first element that is >= val
template <typename T>
CUDA_HOST_DEVICE uint32 lower_bound(const T *data, uint32 size, const T val)
{
    uint32 first = 0;
    uint32 last = size;

    while(last - first > 0)
    {
        uint32 i = first + ((last - first) / 2);

        if (data[i] < val)
        {
            if (i == first)
            {
                first++;
            } else {
                first = i;
            }
        } else {
            if (i == last)
            {
                last--;
            } else {
                last = i;
            }
        }
    }

    return last;
}

} // namespace lift