Home >Common Problem >What is the time complexity of a program using the binary search algorithm?

What is the time complexity of a program using the binary search algorithm?

青灯夜游
青灯夜游Original
2021-01-26 11:35:4633756browse

The time complexity of a program using the binary search algorithm is "logarithmic level". Binary search is a highly efficient search method. The algorithm complexity is the number of while loops. The time complexity can be expressed as "O(h)=O(log2n)".

What is the time complexity of a program using the binary search algorithm?

The operating environment of this tutorial: Windows 7 system, Dell G3 computer.

The time complexity of a program using the binary search algorithm is "logarithmic level".

Related recommendations: "Programming Learning"

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.

Search process:

First, assuming that the elements in the table are arranged in ascending order, compare the keyword recorded in the middle of the table with the search keyword, if they are equal , then the search is successful; otherwise, the middle position record is used to divide the table into the front and last sub-tables. If the keyword of the middle position record is greater than the search keyword, then the previous sub-table is further searched, otherwise the latter sub-table is further searched. 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 complexity:

The basic idea of ​​binary search is to divide n elements into two roughly equal parts, and compare a[n/2] with x , if x=a[n/2], then x is found and the algorithm terminates; if x80c5166f26f05f829738903dccb3fb72a[n/2] , then just search for x in the right half of array a.

The time complexity is the number of while loops.

There are n elements in total,

gradually follows n, n/2, n/4,....n/2^k (the remaining number of elements will be operated next ), where k is the number of loops

Since after you round n/2^k>=1

, you can get n/2^k=1

k=log2n, (based on base 2, the logarithm of n)

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

as follows Provide a piece of pseudo code for the implementation of binary search:

BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max

The half-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. In the worst case, O (log n) completes the search task. 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

If you want to read more related articles, please visit PHP Chinese website! !

The above is the detailed content of What is the time complexity of a program using the binary search algorithm?. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn