I believe that everyone has experienced the pain of finding things. Most people also feel the convenience brought by computer participation in data management, and learning programming has also been added for a problem (such as implementation "if there is no existence." Such an algorithm describes the primary stage of the arrangement of combined algorithms to achieve overview. There is such code in SGI-STL STL_ALGO.H:
Template
Inline _inputiter find (_inputiter __first, _inputiter __last,
Const _TP & __VAL,
INPUT_ITERATOR_TAG)
{
While (__first! = __last &&! (* __first == __val))
__first;
Return __first;
}
This should be able to find the code on all the order we have written, regarding why this looks, "C Shen Shu" Chapter 17 has a detailed description. Perhaps the STL code of the VC6 is more likely to understand:
Template
_Ii find (_ii _f, _ii _l, const _ty & _v)
{for (; _f! = _l; _ f)
IF (* _f == _V)
Break;
Return (_f);
If this is the best, however, the above code is just a universal lookup method for rigid data. If we want to faster, you must add a rule to the data, so we can use rules to improve lookup efficiency. O (n) and o (logn) are not in the same day, not to mention o (1).
It is that people's pursuit of speed has led to this part of the three line code to become a large-incomplete large-scale algorithm (in fact, this is not something, 5 minutes waiting is enough to make a man's mad). The significant increase in speed is based on the N a big basis, so that you have to involve the deposit, you can see, the following evolution is because of the intervention of the existence, if you don't pay attention to this, often What we do is doubtful.
Recalling the process of checking the English-Chinese Dictionary will help us find some finding strategies - the theory comes from practice, it seems that no one will have any objection to this sentence?
First of all, the text of the dictionary is in order of the dictionary (this proposed method, and the sorting method of the dictionary is called the dictionary order, then I said that the dictionary is ordered in the dictionary - anyone who checked the dictionary How is it sorted, I will not explain it), so some English-Chinese Dictionary is not a directory - as long as the foreword and appendix are not too much, there will be no directory - I don't have a directory. How do you check it?
In general, you will turn less, p-head, p-head, if the last word of the current page (generally in the upper right corner of the page), in front of the list, Turn - How many pages it is estimated - if the first word of the current page is behind the word, go forward - how many pages are estimated. Repeat this process until the checked word is between the first and last words of the current page, and then lookup in the current page - this process can also be compared before, but it is usually searched later.
Recalling this process, we can get a lot of inspiration, first of all, "Discount half-find" thinking.
Folding half lookup
The current value is greater than the value value, and it is less than searching, which is the basic idea of folding. I want to spend a lot of brain cells for this algorithm. It seems that I am too stupid:
INT Binfind (int A [], int N, int x) {
INT Low = 0, high = n - 1, mid;
While (low <= high)
{
MID = (low high) / 2;
IF (a [MID] == x) Return MID;
IF (a [MID] Else High = MID - 1; } Return n; } It is not written in the form of a template because it supports a lot of restrictions, which is very suitable for applicable scope, but it is easy to understand. Note that the "Treasure Dictionary" forward (back) The number of pages that are estimated, and a dictionary skilled person and a generic difference is often reflected here. In the computer, this "estimate" is interpolated. This is easy to understand - a book 1000 pages, how to turn it quickly to page 300? Obviously, turned to a place with 3/10 of the book, of course, this will not be very accurate, but it is already close to page 300. The revelation of this example is that in a homogeneous sequence, the interpolation should be valid. INT INSFIND (Int a [], int N, int x) { INT Low = 0, high = n - 1, mid; IF (x> a [high]) return n; / / prevent offshore While (low { MID = Low (X - a [low]) * (high - low) / (a [high] - a [low]); IF (a [MID] == x) Return MID; IF (a [MID] Else High = MID - 1; } Return n; } test program #include #include #include #include "find.h" #define n 30000 INT A [N]; Class Timer // Unit MS { PUBLIC: Void start () {start_t = clock (); Clock_t time () {return (clock () - start_t); Private: Clock_t start_t; } int main () { Timer Timer; INT I, T; For (i = 0; i Timer.Start (); // for (i = 0; i T = Timer.Time (); Printf ("n =% D% DSEQFIND TIMESPARED:% DMS / N", N, N, T); // Printf ("% d", a [seqfind (A, N, 2763)]); Timer.Start (); For (i = 0; i T = Timer.Time (); Printf ("n =% D% dbinfind Timespared:% DMS / N", N, N, T); // Printf ("% d", a [binfind (A, N, 2763)]); time.start (); For (i = 0; i T = Timer.Time (); Printf ("n =% D% DINSFIND TIMESPARED:% DMS / N", N, N, T); // Printf ("% D", A [Insfind (A, N, 2763)]); Return 0; } Test Results N = 30000 30000seqfind Timespared: 12107ms N = 30000 30000binfind Timespared: 40ms N = 30000 30000insfind Timespared: 10ms Note that this test contains the situation of finding failed, otherwise the performance of simple order looks is not as bad.
