Search Process with the result as Boolean Value
The search process in a singly linked list is done as follows:
We return a Boolean value, either true or false.
- Assign a variable ‘curr’ to be the current node that we are traversing. Since we start traversing from the head of the linked list, initialize curr as the head node.
- Loop while ‘curr’ is not a null value - None in Python
- Check if the value stored inside the curr node is equal to the search value.
If the value is the same, return true
- Reassign curr to be the next node, by setting curr to be the next member of curr.
- At the end of the loop, return false, since the value was not found in this linked list.
We use the Boolean method to return the results of this search so we can know whether the particular value was found in the list. If we were able to find this particular value, the return value of the function is the boolean True.
If there was no such element in the list, the return value of the function is the boolean False.
The above-described procedure is applicable if the values can be compared directly.
For an integerlinked list
, we can use the process as is, since integers can be compared easily, and 2 == 2 will always be true.
However, for float linked lists
, it is difficult to compare the float values since there could be an error in floating-point precision, leading to us not getting a match for 2 otherwise equal floats.
To compare floats, we can change the procedure. Instead of comparing the value by equality, we designate some particular range in which we assume two floats to be equal.
Assign a value to variable epsilon corresponding to our margin of error - for example, we could take epsilon = 0.0001. Now, in Step 2.1 for the above algorithm, instead of comparison with the == operator, we define a function called compare(a, b).
This function takes two values a and b and returns true if the difference between them is less than epsilon, and false otherwise.
Thus, we are able to perform comparisons for floating-point data accurately.
A sparse table is a data structure used to quickly
perform range-based queries like range minimum or range maximum.
A sparse table is a form of dynamic programming, where we precompute the required answer for a particular set of queries, through which we can compute the answer for all possible queries.
A sparse table is implemented as a 2D array. The length of the array is equal to the number of elements, and the breadth of the array is equal to the log (base 2) of the number of elements.
The idea is such: suppose we have a query - example minimum of a range.
The sparse table value at row I and column j, store the minimum value found starting at element I, and for a number of elements equal to 2^j.
Thus, when any particular range minimum is required, the range can be broken down into a number of ranges such that each sub-range is a power of 2.
For example, if we want to find the minimum number of values from index 10 - 21. This includes 12 values. We can break this down into 8 + 4 values, and then look up the sparse table for row 10, column 3: since 2^3 = 8. This gives us a minimum of range 10 - 17.
We then look up the sparse table for row 18, column 2, since 2^2 = 4.
Now, this gives us the minimum for the range 18 - 21. We compare these two minimums and find the minimum of these two values. This value is our range minimum.
The runtime of these operations in O(log N), where N is the length of the range. This is much better than O(N) which would otherwise be the runtime of the minimum operation without using the sparse table.
The sparse table has many uses. It can be used to find the minimum in a range, the maximum, or any other range-based query very quickly. It is especially useful in situations where we enter data once and then want to perform many queries. It can also be used for other range queries like the maximum positive number in a range or the minimum number in a range greater than 4.
Thus, the sparse table has many uses. The only limitation is the amount of space used and the time required to set up the sparse table.