Shulou(Shulou.com)06/02 Report--

Editor to share with you about the order table half search for what is the use, I believe that most people do not understand, so share this article for your reference, I hope you will learn a lot after reading this article, let's go to know it!

Half search of the ordered table: take the intermediate value as the comparison object, and if the keyword of the given value is equal to the keyword of the intermediate value, the search is successful; if the given value is less than the keyword of the intermediate record, the search continues in the left half of the intermediate record.

Halved search concept:

Half search, also known as binary search.

The premise is that the records in the linear table must be key ordered (from small to large or from large to small), and the linear table must be stored sequentially.

The basic idea of half-and-half search is: in an ordered table, the intermediate value is taken as the comparison object, and if the keyword of the given value is equal to the keyword of the intermediate value, the search is successful; if the given value is less than the keyword of the intermediate record, the search continues in the left half of the intermediate record; if the given value is greater than the keyword of the intermediate value, the search continues in the right half of the intermediate record. Repeat the above process until the search is successful, or there is no record for all areas, and the search fails.

Implementation of the algorithm:

Public int Binary_Search (int [] a, int n, int key) {int low = 1, high = n, mid;while (low a [mid]) {low = mid + 1;} else return mid;} return 0;}

Three pointers low,high,mid are usually used. Represents the leftmost subscript of the search area, and the rightmost subscript of the lookup area, which has been compared to the current value subscript.

Time complexity analysis:

Half search is actually equivalent to dividing the static sequential search table into two sub-trees, that is, the search process only needs to find half of the data, which is equal to a half less workload to improve efficiency.

The above is all the contents of this article entitled "what is the use of half-searching an ordered table?" Thank you for your reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.