Правильно разместите элемент в массиве в порядке возрастания - PullRequest
Новая
       6

Правильно разместите элемент в массиве в порядке возрастания

0 голосов
/ 10 октября 2019

Я работаю с Solidity , очень простым языком, полным по Тьюрингу, без причудливых функций массива прототипов, предлагаемых ему другими языками, такими как find в JavaScript. Я также должен сделать так, чтобы эта функция размещения выполняла как можно больше циклов или рекурсий (что разрешено в Солидности), поскольку в процессе используется вещь, называемая «газ», которая является частью криптовалюты.

В основномЯ должен правильно разместить элемент в массиве в порядке возрастания, чтобы элемент перед ним был меньше, а элемент перед ним был больше. И если элемент, который я пытаюсь разместить, равен найденному элементу, то просто вернуть позицию этого элемента. Я не ожидаю большого количества элементов в этом массиве, никогда не превышающего 1000, но даже 100 элементов и полные 100 итераций чрезвычайно дороги , и, поскольку все затраты на поиск относятся к пользователю, этов мою пользу, чтобы сделать это как можно более эффективным.

Я понимаю алгоритмы сортировки, но здесь мы используем предварительно отсортированный массив, поскольку каждый элемент, который будет добавлен в этот массив, будет сортироваться один за другим со временем. Теперь, что я придумал, и я не знаю имени для этого, чтобы разделить длину массива пополам, выполнить условие;сравните его со следующим значением или значением под ним и затем разделите или умножьте деление на половину его значения, затем снова проверьте соседей и умножьте или разделите на половину, половину деления и так далее, пока я не получу правильное значение.

Будет ли это работать? Как это называется?

Для справки 

function FindSpotinArray(uint256 price,
    uint256 divisionVariable, 
    uint256[] priceArray) returns (uint256) {
    if(price < priceArray[x] && priceArray != priceArray[x]) {
        divisionVariable * 2;
        var x = priceArray / divisionVariable;
    } else if (price > priceArray[x] && priceArray != priceArray[x]) {
        divisionVariable / 2;
        var x = priceArray / divisionVariable;
    } else if (price == priceArray[x]) {
        return x;
    } else if (priceArray[x - 1] <= priceArray[x] <= priceArray[x + 1]) {
        return x;
    }
}
...