线性搜索与二分搜索

1. Overview

Search problems are some of the most common in programming, and there are many ways to solve them. Two of these ways are Linear Search and Binary Search.

In this tutorial, we’re going to explain the two methods and provide a comparison between them.

2. Linear Search

2.1. Theoretical Idea

Linear Search scans one item at a time and can be used to solve any kind of search problem.

2.2. Linear Search in an Array

We can use Linear Search to look for a value inside an array. We iterate over all the elements of the array and stop when the searched value is found. However, note that no conditions are needed to use this kind of search.

Let’s take a look at the implementation of the discussed algorithm:

algorithm LinearSearch(A, n, value):
    // INPUT
    //   A = The array to search for the value inside
    //   n = The length of the array
    //   value = The value to search for
    // OUTPUT
    //   Returns the index of the element if found, or -1 otherwise

    for i <- 1, 2, ..., n:
        if A[i] = value:
            return i

    return -1

The total time complexity of the above algorithm is , where is the total number of elements in the array.

2.3. Linear Search for an Answer

Let’s take an example to explain this idea.

Suppose we want to make bottles of fruit juice of determined sizes. We have some amount of money, and there’s a shop nearby that sells fruits for fixed prices. We want to know the maximum number of bottles we can make.

To simplify the problem, we’ll assume that there’s a function that takes the number of bottles as input. This function returns true if the money we have is enough to make that number of bottles, and returns false otherwise.

Then, we’ll iterate over the range from the lowest possible number to the maximum possible number of bottles we can make and check every value with the function. We’ll keep iterating until the function returns false, then we’ll stop the algorithm and return the maximum possible number of bottles we can make with the money we have.

Let’s take a look at the implementation of the discussed algorithm:

algorithm FindMaxAcceptedAnswer(low, high):
    // INPUT
    //   low = The lowest possible answer for the problem
    //   high = The highest possible answer for the problem
    // OUTPUT
    //   Returns the maximum value in range [low, high] that is accepted by the function canMake,
    //   or -1 otherwise

    answer <- -1
    for i <- low, low + 1, ..., high:
        if canMake(i):
            answer <- i
        else:
            break

    return answer

The total time complexity of the above algorithm is , where is the length of the range.

3. Binary Search

3.1. Theoretical Idea

Binary Search’s main idea is to split the search range in half. Then, we check the middle value. Based on the middle value, we decide whether to continue our search inside the left or the right part.

3.2. Binary Search in an Array

Unlike Linear Search, the condition to use Binary Search is that the array should be sorted. Suppose you want to look for a value in an array . First, we define the lowest value of the searched range to be 1, which is the smallest index inside the array. Also, we define the highest value to be , where is the number of elements in the array, which is the largest possible index inside the array.

After that, we perform multiple steps. In each step, we take the middle element and check if it’s the value we are searching for. If yes, we return its index and the algorithm stops.

If not, there are two options. If this middle element is greater than the searched value, then we have to search in the left part of the range. Otherwise, if this middle element is smaller than the searched value, then we’ll search in the right part.

Let’s take a look at the implementation of the discussed algorithm:

algorithm BinarySearch(A, n, value):
    // INPUT
    //   A = The array to search for the value inside
    //   n = The length of the array
    //   value = The value to search for
    // OUTPUT
    //   Returns the index of the element if found, or -1 otherwise

    low <- 1
    high <- n
    answer <- -1

    while low <= high:
        mid <- (low + high) / 2
        if A[mid] = value:
            answer <- mid
            break
        else if A[mid] < value:
            low <- mid + 1
        else:
            high <- mid - 1

    return answer

The total time complexity of the above algorithm is , where is the total number of elements in the array.

3.3. Binary Search for an Answer

We can’t always use Binary Search to look for an answer to a problem because there’s a condition that should be met. The condition states that the range in which we search for a specific value must have exactly one accepted continuous part and exactly one unaccepted continuous part.

Let’s take the same example as in Linear Search for an answer and apply binary search on the range of values.

Firstly, we assume that we have the same function we mentioned earlier. Secondly, we define the lowest and the highest number of fruit juice bottles.

Thirdly, we will perform multiple steps. In each step, we’ll take the middle value of the range and check it with the function. If the function returns true, it means the maximum number of bottles to be made is either this value or a value that is even larger. Therefore, we search in the right part of the range.

Otherwise, it means that this number of bottles can’t be made, and we need to try and reduce the number of bottles to make. In this case, we’ll search on the left part.

We repeat this process until the condition is not met anymore. Thus, in this way, the maximum number of bottles we can make will be stored inside the variable.

Let’s take a look at the implementation of the discussed algorithm:

algorithm BinarySearchForProblemAnswer(low, high):
    // INPUT
    //   low = The lowest possible answer for the problem
    //   high = The highest possible answer for the problem
    // OUTPUT
    //   Returns the maximum value in range [low, high] that is accepted by the function canMake,
    //   or -1 otherwise

    answer <- -1

    while low <= high:
        mid <- (low + high) / 2
        if canMake(mid):
            answer <- mid
            low <- mid + 1
        else:
            high <- mid - 1

    return answer

The total time complexity of the above algorithm is , where is the length of the search range.

4. Comparison

Taking a look at the table, we see the main differences between Binary Search and Linear search.

Linear Search

Binary Search

Array Search

No conditions

The array must be sorted

Answer search

No conditions

The answer range must have
one continuous part that is
accepted as an answer,
and one continuous part
that is not accepted

Time Complexity

In other words, it’s best to solve a problem with Binary Search if possible because of its lower complexity.

5. Conclusion

In this tutorial, we explained the Linear Search and Binary Search theoretically. Then, we talked about search in an array and search for the answer to a problem. After that, we saw how to solve each problem using the two search methods.

Finally, we presented a basic comparison between the two approaches.