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

I would like to share with you what the time complexity of a program that uses the binary search algorithm refers to. I believe most people don't know much about it, so share this article for your reference. I hope you will gain a lot after reading this article. Let's learn about it!

The time complexity of a program that uses a binary search algorithm is "logarithmic". Binary search is an efficient search method. The complexity of the algorithm is the number of while cycles, and the time complexity can be expressed as "O (h) = O (log2n)".

The time complexity of a program that uses a binary search algorithm is "logarithmic".

Correlation

Binary search, also known as half search (Binary Search), is a more efficient search method. However, half-and-half lookup requires that the linear table must have a sequential storage structure, and the elements in the table are arranged in order by keyword.

Search process:

First of all, assuming that the elements in the table are arranged in ascending order, compare the keywords recorded in the middle of the table with the search keywords, and if the two are equal, the search is successful; otherwise, the table is divided into the first and the last two sub-tables by using the intermediate location records. if the keyword of the intermediate location record is greater than the search keyword, then further look for the previous sub-table, otherwise further look for the latter sub-table. Repeat the above process until a record that meets the criteria is found, making the search successful, or until the child table does not exist, where the lookup is not successful.

Algorithm complexity:

The basic idea of binary search is to divide n elements into two parts that are roughly equal, and compare a [nprime 2] with x, if x is found and the algorithm is aborted if x is found and the algorithm is aborted. If xa [nhand 2], then just search for x in the right half of the array a.

The time complexity is the number of while loops.

There are altogether n elements.

Gradually, it will be followed by n-magic, 2-pound, 4-pound, n / 2 ^ k (the remaining number of operating elements), where k is the number of cycles.

Because your n / 2 ^ k is rounded > = 1

Even if n / 2 ^ k = 1

Available k=log2n, (with 2 as the base, the logarithm of n)

So the time complexity can be expressed as O (h) = O (log2n).

The following provides a piece of pseudo code for the binary lookup implementation:

BinarySearch (max,min,des) mid-

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.