Búsqueda binaria en arreglos de Solidity

No, todos los tipos de datos de recopilación son muy básicos. Esto puede considerarse una decisión de diseño para mantener la ejecución muy económica y, por lo tanto, no cambiará en el futuro. Que yo sepa, aún no se ha publicado ninguna biblioteca para la búsqueda binaria en tipos de datos. Lo único similar que conozco es el mapa iterable implementado como biblioteca: https://solidity.readthedocs.io/en/latest/frequently-asked-questions.html#are-mapping-s-iterable

Hay una implementación de búsqueda binaria para arreglos de enteros ordenados, aquí .

Tenga en cuenta que esto es solo una búsqueda, y tendrá que cambiar el tipo/estructura de datos manejados inta cualquiera que sea su estructura.

OpenZeppelin escribió un algoritmo de búsqueda binaria en Solidity v0.8. Aquí está su implementación (código tomado de aquí ):

function findUpperBound(uint256[] storage array, uint256 element) internal view returns (uint256) {
    if (array.length == 0) {
        return 0;
    }

    uint256 low = 0;
    uint256 high = array.length;

    while (low < high) {
        uint256 mid = Math.average(low, high);

        // Note that mid will always be strictly less than high (i.e. it will be a valid array index)
        // because Math.average rounds down (it does integer division with truncation).
        if (array[mid] > element) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    // At this point `low` is the exclusive upper bound. We will return the inclusive upper bound.
    if (low > 0 && array[low - 1] == element) {
        return low - 1;
    } else {
        return low;
    }
}

Y si te preguntas qué Math.averagees, mira esto .

Creé un árbol de estadísticas de pedidos que resuelve una serie de problemas, como encontrar la mediana o el rango de un valor en una lista ordenada, al mismo tiempo que proporciona un método para limitar el costo de la gasolina a un límite absoluto máximo/peor de los casos en cualquier escala .

Este repositorio se basa en Red Black Tree de Bokky Poobah, que proporciona la base para el árbol de autoequilibrio. https://github.com/rob-Hitchens/OrderStatisticsTree