library Arrays {
/**
* @dev Upper bound search function which is kind of binary search algorithm. It searches sorted
* array to find index of the element value. If element is found then returns its index otherwise
* it returns index of first element which is greater than searched value. If searched element is
* bigger than any array element function then returns first index after last element (i.e. all
* values inside the array are smaller than the target). Complexity O(log n).
* @param array The array sorted in ascending order.
* @param element The element's value to be found.
* @return The calculated index value. Returns 0 for empty array.
*/
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;
}
}
}
/**
 * @title Arrays
 * @dev Utility library of inline array functions
 */
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;
}
}
/**
 * @dev Upper bound search function which is kind of binary search algorithm. It searches sorted
 * array to find index of the element value. If element is found then returns its index otherwise
 * it returns index of first element which is greater than searched value. If searched element is
 * bigger than any array element function then returns first index after last element (i.e. all
 * values inside the array are smaller than the target). Complexity O(log n).
 * @param array The array sorted in ascending order.
 * @param element The element's value to be found.
 * @return The calculated index value. Returns 0 for empty array.
 */