二分查找的复杂度 | Baeldung中文网

1. Introduction

In this tutorial, we’ll derive the complexity of binary search.

2. Binary Search

Binary search is an efficient algorithm for finding the position of an item in a sorted array.

So, in this problem, we have a sorted array (such that $a_1 \leq a_2 \leq \ldots a_n$ ) and a search key . We want to find if is in and at what position.

The assumption is the input array is sorted, which requires its elements to be comparable. So, there has to be an ordering relation on the class of elements from which we draw and .

3. The Algorithm

Binary search compares to the middle element $a_{middle}$ of the array and focuses on the left or right subarrays depending on whether $x < a_{middle}$ or $x > a_{middle}$ . If $a_{middle} = x$ , we output middle :

Here’s the pseudocode:

algorithm BinarySearch(a, x):
    // INPUT
    //     a = a sorted array, indexed from 1 to n, where a[i] <= a[i+1]
    //     x = the search key
    // OUTPUT
    //     the index of x in a if x is in a, or 'failure' otherwise

    left <- 1
    right <- n
    middle <- (left + right) / 2

    while left <= right:
        if x < a[middle]:
            // All the elements a[middle], ..., a[right] are > x
            right <- middle - 1
        else if x > a[middle]:
            // All the elements a[left], ..., a[middle] are < x
            left <- middle + 1
        else:
            // x = a[middle]
            return middle
        middle <- (left + right) / 2

   // x not in a
   return 'failure'

So, the search stops when there are no more elements to search, or we find the search key.

4. Complexity

Let’s call $a[left, left + 1, \ldots, right]$ the active part of the array. Since $middle = \lfloor \frac{left+right}{2} \rfloor$ , we halve the active part in each iteration:

In the worst case, isn’t in the array, so the number of iterations is $\lceil \log_2 n \rceil + 1$ :

$\lceil \log_2 n \rceil$ iterations to get to a one-element sub-array with
One additional iteration to break the loop

We do an O(1) work in each iteration by comparing to the middle elements. So, the algorithm is logarithmic: $\boldsymbol{O(\log n)}$ .

4.1. Master Theorem

We can use the Master Theorem to find the complexity. Let T(n) be the number of comparisons we perform in the worst case if the input array has elements.

Since we halve the active part and do at most two comparisons in each iteration, the recurrence is:

[T(n) = T(n/2) + 2]

The theorem uses the generic form:

[T(n) = a T(n/b) + f(n)]

and compares f(n) to $n^{\log_b a}$ . In our case, a=1 and b=2 , so $n^{\log_b a}=n^{\log_2 1} = n^0 = 1$ , and $f(n)=2 \in \Theta(1)$ .

Therefore, it holds that:

$[2 = f(n) \in \Theta(1) = \Theta \left(n^{\log_2 1} \right)]$

From the Master Theorem, we get the following:

$[T(n) \in \Theta(n^{\log_b a} \log n)=\Theta(n^0 \log n) = \Theta(\log n)]$

4.2. Space Complexity

The binary search uses only a constant number of helper variables ( left, middle, right, n ). As a result, its iterative version (which we presented) has an O(1) auxiliary space complexity.