Suppose we need to find out whether the email address “ demensdeum@gmail.com ” belongs to the list of allowed email addresses for receiving letters.
We sort through the entire list from the first to the last element, checking whether the element is equal to the specified address – we implement the linear search algorithm. But will it be long or not?
To answer this question, use the “Temporary complexity of the algorithms”, “O” notation. In the worst case, the linear search operation time is equal to the nth number of array elements, we write this in the “O” notation – O (n). Next, you need to clarify that for any known algorithm, there are three performance indicators – execution time in the best, worst, and average cases. For example, the mail address “ demensdeum@gmail.com ” is in the first index of the array, then it will be found in the first step of the algorithm, it follows that the execution time in at best, O (1); and if at the end of the list, then this is the worst case – O (n)
But what about the details of the software implementation, the performance of the hardware, should they affect big O? Now exhale and imagine that the calculation of time complexity is calculated for some abstract ideal machine, in which there is only this algorithm and nothing more.
Algorithm
Ok, it turns out that the linear search is rather slow, let’s try using the binary search. To begin with, it should be clarified that we will not work with binary data, this name was given to this method because of the features of its work. Initially, we sort the array into lexicographically , then the algorithm takes the range of the entire array, gets the middle element of the range, compares it lexicographically , and depending on the result comparison decides what range to take to search for more – the top half of the current or lower. That is, at each step of the search, a decision is made of two possible ones – binary logic. This step is repeated until either the word is found or not found (the intersection of the lower and upper indices of the range will occur).
The performance of this algorithm is the best case when an element is immediately found in the middle of the O (1) array, the worst case is O (log n)
Gotchas
When implementing binary search, I came across not only the interesting problem of the lack of standardization of lexicographic comparison in programming language libraries, but I even found that there is no single standard for implementing localeCompare inside JavaScript . The ECMAScript standard allows different implementations of this function, because of this, when sorting using localeCompare, absolutely different results can be observed on different JavaScript engines.
Therefore, for the algorithm to work correctly, you must sort and use only the same lexicographic comparison algorithm in your work, otherwise nothing will work. So, for example, if you try to sort an array in Scala, and search using nodejs without realizing your own sorting / sorting of one implementation, then you will not expect anything other than disappointment in humanity.
References
https://en.wikipedia.org/wiki/Lexicographical_order
https://en.wikipedia.org/wiki/Binary_search_algorithm
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript
Source Code
https://gitlab.com/demensdeum/algorithms
