In the case of search at different probability ASL takes minimum value at this case: SS Pn≥Pn12…2P2≥P1 According to records' search probability in the table, re-arrange them from small to big to Improve efficiency If unable to determine the search probability in advance, then the method of improving search process is that: after each search, just to put the records searched to the end of the table position
In the case of search at different probability， ASLss takes minimum value at this case: Pn≥Pn-1≥···≥P2≥P1 According to records’ search probability in the table, re-arrange them from small to big to improve efficiency. If unable to determine the search probability in advance, then the method of improving search process is that: after each search, just to put the records searched to the end of the table position
Search of ordered sequential lists The search algorithm of sequential lists is easy, but ASL is too large, it isn't fit for long sequential lists If the sequential lists is in order, then the process of search can be based on"binary Binary searc h Search process: reduce the range of pre-search record to the half Application condition the storage structure is ordered sequential lists
The search algorithm of sequential lists is easy , but ASL is too large, it isn’t fit for long sequential lists. If the sequential lists is in order , then the process of search can be based on “binary”. ▪Search of ordered sequential lists Binary search Search process: reduce the range of pre-search record to the half. Application condition : the storage structure is ordered sequential lists
Implementation of binary search algorithm 1. Assume that table length is n low, high and mid denote upper bound, lower bound and middle point of the pre-search records range, and k is the giving value. 2.at the beginning, set low=1, high=n, mid=(low+high)/2I compare k with the record pointed by mid if ke--rImidJ key, search success else if k<rlmid]- key, then high=mid-1 else if krmid] key then low-mid+1 3. Repeat the above-mentioned operation until low>high search failure
1.Assume that table length is n，low、high and mid denote upper bound, lower bound and middle point of the pre-search record’s range, and k is the giving value. 2.at the beginning, set : low=1,high=n,mid=(low+high)/2 compare k with the record pointed by mid if k==r[mid].key，search success else if k<r[mid].key，then high=mid-1 else if k>r[mid].key，then low=mid+1 3. Repeat the above-mentioned operation until low>high , search failure Implementation of binary search algorithm
Such as: key =21 process of search 找21 例 1234567891011 513192137566475808892 low mid high 23456 1011 513192137566475808892 lo id high 1234567891011 513192137566475808892 low mid high low Instruct the lower bound of the search range high Instruct the upper bound of the search range mid=(oW+high)/2
low mid high 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找21 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high Such as: key =21 process of search low Instruct the lower bound of the search range high Instruct the upper bound of the search range mid = (low+high)/2
key=70: Process of search #70 1234567891011 513192137566475|8088|92 low mid high 1234567891011 513192137566475808892 low high 1234567891011 513192137566475808892 low mid high 1234567891011 513192137566475808892 low high mid
key =70 :Process of search 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 lowhigh mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high