binary search algorithm

Binary search is also called 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, record the key in the middle of the table The word is compared with the search keyword. If the two are equal, the search is successful; otherwise, the middle position record is used to divide the table into the first and last sub-tables. If the keyword recorded in the middle position is greater than the search keyword, the previous sub-table is further searched. , otherwise search further for the next sub-table. 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.

Number of comparisons

Calculation formula:

When the sequence table has n keywords:

When the search fails, compare the keyword at least a times; when the search succeeds, the maximum number of keyword comparisons is b.

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

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 is terminated; if xa[n/2], Then just search for x in the right half of array a.

The time complexity is nothing more than 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)

The following provides a bisection Find the pseudocode of the implementation:

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, which can complete the search task in O(log n) in the worst case. 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

The above is the detailed content of binary search algorithm. For more information, please follow other related articles on the PHP Chinese website!