Searching for a value in a dynamic array

Question

I understand that for loops on dynamic arrays are a big no no in Solidity, so I am trying to find an alternative to this problem.

Goal:

From a dynamic array of numbers, I am trying to extract the index of the element that is "closest" to another number (number). In JavaScript terms, this would look like:

let number = 21;
let closest;
let array = [5, 10, 15, 20, 25]; // using fixed size as an example, but array could be 1000+ in length
for (let i = 0, i < array.length, i++) {
  let difference = Math.abs(number - array[i]); // remove integer sign for comparison
  if ( !closest || difference < closest )
    closest = i;
  }
}

Looking through Solidity docs and other questions here, it seems that this may be an extremely gas expensive task with no alternative.

Is there another way of looking at this problem with a Solidity hat on?

Answer 1

You are right about avoiding iteration. The trick is to ensure a finite maximum cost at any scale. Generally, that means organizing things so data is handy with limited iteration and recursion.

pragma solidity 0.5.16;

import "./HitchensOrderStatisticsTree.sol";

contract Nearest {

    using HitchensOrderStatisticsTreeLib for HitchensOrderStatisticsTreeLib.Tree;
    HitchensOrderStatisticsTreeLib.Tree tree;

    /**
     * It sorts key/value pairs.
     * You may have duplicate keys or duplicate values, 
     * but you cannot have dublicate key/value pairs.
     */

    function insert(uint value, bytes32 key) public {
        tree.insert(key,value);
    }

    function nearest(uint search) public view returns (uint value) {
        uint rank = tree.rank(search);
        value = tree.atRank(rank);

        /**
         * We have a match or the nearest higher number.
         * Will return the highest number if the search is out of range. 
         * Quick hack to switch to next lower:
         */

        if(search != value && rank > 0) rank -= 1;
        value = tree.atRank(rank);

        /**
         * We have a match or the nearest lower number.
         * will return the lowest number if the search is out of range.
         */
    }
}

This library maintains a balanced b-tree (red-black). https://github.com/rob-Hitchens/OrderStatisticsTree

A b-tree is an O(log n) structure and you want it to be O(1) for the EVM. Constraining the maximum cost is an app-level concern. There are multiple ways to do that, so some strategies for handling it are suggested in the README. The main concern is limiting the maximum number of nodes (depth) in the tree. The library is reasonably performance-optimized at the design and implementation levels.

There is a lot going on in those libraries and you can remove superfluous functions if you don't need them. The "Statistics" aspect demonstrates how to populate the tree with metadata to enable different kinds of analysis. Alternatively, try https://github.com/bokkypoobah/BokkyPooBahsRedBlackTreeLibrary which it is based on. It is a pure sorter without keys, counts, ranks, etc.

You'll notice the bytes32 keys. Those are there to help bind sorted values with application data. They usually a point to a record somewhere, e.g. orderId. Keys are not important for the Nearest.sol example so send any valid input but make sure all key/value pairs are unique.

From eyeballing your example, I got the impression you want the match or the nearest lower number. The library returns the nearest higher number, so I made a little fudge to nudge it lower, if needed, without altering the library itself.

An explainer about what's going on: https://hackernoon.com/binary-search-trees-and-order-statistics-for-ethereum-db47e2dd2c36

Hope it helps.