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

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)".

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 xa[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!