Python detailed analysis of binary search algorithm

This article brings you relevant knowledge about python, which mainly organizes issues related to the binary search algorithm, including algorithm description, algorithm analysis, algorithm ideas, etc. The following is Let's take a look, hope it helps everyone.

Recommended learning: python video tutorial

1. Algorithm description

The dichotomy is one A relatively efficient search method

Recall the number-guessing mini-game that you have played before. A positive integer x less than 100 is given in advance, and you will be given prompts to judge the size during the guessing process, and ask you how Guess it quickly?

The game we played before gave 10 chances. If we learn the binary search method, no matter what the number is, it only takes 7 times at most to guess the number.

2. Algorithm analysis

1. It must be an ordered sequence.

2. There are requirements for the amount of data.

The amount of data is too small and not suitable for binary search. Compared with direct traversal, the efficiency improvement is not obvious.

It is not suitable to use binary search if the amount of data is too large, because arrays require continuous storage space. If the amount of data is too large, continuous memory space to store such large-scale data is often not found. .

3. Algorithm idea

Suppose there is an ordered list as follows:



Is the number 11 In this list, what is its index value?

4. Code implementation

Pure algorithm implementation

Implementation code ：

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]# 需要查找的数字seek_number = 11# 保存一共查找了几次count = 0# 列表左侧索引left = 0# 列表右侧索引right = len(arr_list) - 1# 当左侧索引小于等于右侧索引时while left  arr_list[middle]:
        # 左侧索引为中间位置索引+1
        left = middle + 1
    # 如果查找的数字小于中间位置的数字时
    elif seek_number <p>Run result:</p><p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/000/067/ab7ca007166584d2196443b3030f239a-4.png" class="lazy" alt="Python detailed analysis of binary search algorithm"></p><h2 id="Recursive-method-implementation">Recursive method implementation</h2><blockquote><p>A variable count is defined in the loop. If the first The count does not change after the loop, which means that the input is an ordered sequence. At this time, we directly return to exit the loop. The time complexity at this time is O(n)</p></blockquote><p>Implementation code: </p> <pre class="brush:php;toolbar:false">arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]def binary_search(seek_number, left, right):
    if left  arr_list[middle]:
            left = middle + 1
        else:
            return middle        # 进行递归调用
        return binary_search(seek_number, left, right)
    # 当左侧索引大于右侧索引时，说明没有找到
    else:
        return -1# 查找的数字seek_number = 11# 列表左侧索引left = 0# 列表右侧索引right = len(arr_list) - 1print("查找的数字：%s，索引为：%s" % (seek_number, binary_search(seek_number, left, right)))

Running results:

Recommended learning:python video tutorial

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