You should be familiar with the concept of [Boundary Value Analysis](/codex/boundary-value-analysis).
For partitions of multi-dimensional variables, the concepts of Equivalence Partitioning and Boundary Value Analysis generalize. We consider four types of values or points that can be tested with respect to a given equivalence class:
- "In" points – values inside the equivalence class
- "Out" points – values outside the equivalence class
- "On" points – values on the equivalence class boundary
- "Off" points – values slightly outside of the equivalence class boundary.
### Worked example
This is an advanced example where the input domain is the set of arrays. We will study the OpenZeppelin function for finding the upper bound in a sorted array.
-- CODE language-solidity --
/**
* @dev Searches a sorted `array` and returns the first index that contains
* a value greater or equal to `element`. If no such index exists (i.e. all
* values in the array are strictly less than `element`), the array length is
* returned. Time complexity O(log n).
*
* `array` is expected to be sorted in ascending order, and to contain no
* repeated elements.
*/
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;
}
}
First, we identify the equivalence classes. They could be as follows:
- Empty array
- Array with a single element `x`
- `x = element`
- `x` < `element`
- `x` > `element`
- Unsorted array (invalid input)
- Sorted array of size ≥ 2
- `element` equal to an element in the array
- `element` larger than smallest element in array, smallest than largest element but not present in array
- `element` larger than all elements in the array
- `element` smaller than all elements in the array
Let's apply Domain Analysis to the equivalence class "Sorted array of size ≥ 2, `element` larger than all elements in the array". In this case the points could be as follows:
- In point: `array=[7, 8, 9], element=15`
- Out point: `array=[7, 8, 9], element=8` (out point of one equivalence class can be the in-point of another)
- On points:
- `array=[7, 8], element=15` (array size minimal)
- `array=[7, 8, 9], element=10` (element minimal)
- Off points:
- `array[7, 8, 9], element=9` (element just too small to fit in equivalence class).
