What are the storage methods and element arrangement requirements for tables suitable for binary search?

The storage method and element arrangement requirements of the table suitable for binary search are: sequential storage, and the elements are in order. Binary search is a more efficient search method, which requires that the linear table must adopt a sequential storage structure, and the elements in the table must be arranged in order by keywords.

Binary search is also called binary search (Binary Search), which is a more efficient search method. However, binary search requires that the linear table must adopt a sequential storage structure, and the elements in the table must be arranged in order by keywords.

First, assuming that the elements in the table are arranged in ascending order, compare the keyword recorded in the middle position of the table with the search keyword. If the two are equal, the search is successful; otherwise, use the middle position record to divide the table into the first, second and third For the latter two sub-tables, if the keyword recorded in the middle position is greater than the search keyword, then the previous sub-table will be searched further, otherwise the latter sub-table will be searched further. Repeat the above process until a record that meets the conditions is found, making the search successful, or until the subtable does not exist, in which case the search fails.

Algorithm requirements

1. A sequential storage structure must be used.

2. They must be arranged in order according to keyword size.

Number of comparisons

Calculation formula:

When the sequence table has n keywords:

When the search fails, at least Compare keywords a times; when the search is successful, the maximum number of keyword comparisons is b.

Note: a, b, n are all positive integers.

Explanation

The halved search method is also called the binary search method. It makes full use of the order relationship between elements and adopts the divide-and-conquer strategy to solve the problem in the worst case. The search task can be completed in O(log n). Its basic idea is: (assuming that the array elements are arranged in ascending order) divide n elements into two halves with roughly the same number, take a[n/2] and compare it with the x you want to find, if x=a[n/ 2] then x is found and the algorithm terminates; if x

For more related knowledge, please visit: PHP Chinese website!

The above is the detailed content of What are the storage methods and element arrangement requirements for tables suitable for binary search?. For more information, please follow other related articles on the PHP Chinese website!