Search algorithm

  • 1. To search one by one; Simple implementation; Too slow
  • Binary search: ordered; Simple; Insert very slow
  • HASH: fast query. Take up space; Not very suitable for storing large-scale data
  • Binary lookup trees: inserts and queries are fast (log(N)); Unable to store large-scale data, complexity degradation
  • Balanced tree: To solve the BST degradation problem, the tree is balanced; When there are many nodes, the tree is still very tall
  • Multi-path search tree: one father multiple child node (degree); If there are too many nodes, the tree height will not be too deep
  • Multi-path balanced lookup Tree B-tree

Binary search

Idea 1: “Direct search”

The first approach is simpler, as soon as we find the element in the body of the loop, we return the result.

  • Take two node centersmid, first look at the center position valuenums[mid].
  • If the center position isnums[mid]With the targettargetEqual,Direct returnThe index of the central location element.
  • If the center position isnums[mid]Less than the target valuetarget, set the left node tomid + 1And then we’re going to continue to the right[mid + 1, right]Search.
  • If the center position isnums[mid]Greater than the target valuetarget, set the right node tomid - 1And then continue on the left[left, mid - 1]Search.
def bin_search(lst, value) :
    left, right = 0.len(lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if value == lst[mid]:
            return mid
        elif value < lst[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return -1
Copy the code

Idea 2: “Elimination”

The second way to think about it is to exclude the target element from the loop body.

  • Take two node centersmidAccording to the judgment conditions, first exclude the interval where the target element does not exist.
  • Then continue to look for elements in the remaining interval and continue to exclude non-existent intervals based on conditions.
  • Until there is only one element left in the range, then determine if that element is the target element.
def search(lst, value) :
    left, right = 0.len(lst) - 1
    Select target from [left, right]
    while left < right:
        mid = (left + right) // 2
        # LST [mid] < mid, left [mid], right [mid + 1
        if lst[mid] < value:
            left = mid + 1
        # LST [mid] is greater than or equal to the target value, the target element may be in [left, mid], search continues in [left, mid]
        else:
            right = mid
    # check whether the remaining elements of the interval are target elements, otherwise return -1
    return left if lst[left] == value else -1
Copy the code

Two ideas are applicable

  • Binary search idea 1: because the judgment statement isleft <= rightSometimes you have to think about returning isleftorright. There are three branches in the loop, and there must be one for exiting the loop or returning directly. This is a good way to solve simple problems. That is, the elements to be found are simple, the array is all non-repeating elements, and= =,>,<The situation is very easy to write about.
  • The idea of binary search 2: more in line with binary search algorithm subtraction thought. Each time exclude the target element must not exist in the interval, to achieve the effect of reducing the scale of the problem. Then continue to look for the target element within the possible range. This approach is suitable for complex problems. For example, if you’re looking for elements in an array that might not exist, if you’re looking for boundary problems, you can use this idea.

The resources

Algorithmic Clearance Manual (LeetCode) : algo.itcharge.cn/01. Array /03. Dichotomy…