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

In this issue, Xiaobian will bring you about how to achieve sequential search in Python. The article is rich in content and analyzed and described from a professional perspective. After reading this article, I hope you can gain something.

Sequential lookup--unordered table

The elements in the unordered table are randomly arranged, that is, the probability of data items appearing in each position in the list is equal. If you want to find a data item in the unordered table, you must first determine whether there is a data item to be found in the unordered table.

Starting from the first data item, compare them one by one in the increasing direction of index. Returns True if found halfway, False if not found at last

Analysis of Disordered List Algorithm

Basic steps of search algorithm: data item comparison

The number of data item comparisons determines the time complexity of the algorithm

Depending on whether the data item is in the list, the number of comparisons is different:

If the data item is not in the list: all elements need to be compared, the number of comparisons n If the data item is in the list: the best case is compared once (the first element); the worst case is compared n times (the last element is)

Because the data items are arranged randomly in the list, the average number of comparisons is n/2.

Time complexity: O(n)

Sequential lookup--ordered table

Ordered table is the ordered arrangement of data items (assuming from small to large). Compared with disordered table, the lookup of ordered table has special places:

When data items exist: alignment process is the same as unordered table

When the data item does not exist: you can use the ordered arrangement to end the search ahead of time

When the data item to be searched (goal_item) is smaller than the data item at the current position, it means that the following ones are larger than it, and there must be none behind, so the search is terminated early and returns False.

The above is how to achieve sequential search in Python shared by Xiaobian. If there is a similar doubt, please refer to the above analysis for understanding. If you want to know more about it, please pay attention to 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.