Shulou(Shulou.com)06/01 Report--

This article mainly shows you "how to use Python language to achieve dichotomy search", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "how to use Python language to achieve dichotomy search" this article.

Foreword:

Dichotomy is also known as dichotomy search, which is a more efficient search method.

If there is a new person in the company, named Zhang San, who is the 47th person in your company, after a period of time, some people, uh, are unhappy with Zhang San and leave, then Zhang San must not be the 47th person in the company at this time. How to know the number of Zhang San platoon? let's use dichotomy to find him out.

Train of thought:

Give you a 1000-page book, randomly given a page number, how to find it in the fastest way? If you look for it step by step, you need to find it up to a thousand times! So how can we use dichotomy to solve this problem? The key to dichotomy is the word dichotomy.

Step 1: set a page number as the central point to divide the 1000 pages into two. The median function is to narrow the search area by half each time, that is, to achieve the square effect. That is, you can use (first + last) / 2 = median.

Step 2: compare the page number you need to find with the median. If it is greater than the median, the search for the first half of the median will be discarded, otherwise, the search for the second half of the range will be abandoned to achieve the prescription effect. Step 3: recalculate the median in the new search area

Step 4: find the median page number comparison and determine the new search scope

Step 5: cycle through the above steps until the page number is found

Code:

Through the above train of thought analysis, we know the dichotomy implementation steps, and then through the code to implement the steps, the first is the loop implementation

# Analog page number array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 6) # first value low = "last value height = len (array) -" setting search page number findNum = "Lookup while True: # get median mid = int ((low+height) / 2) # print median View the number of cycles print (Array [mid]) # if the median is less than the lookup value, lock the second half of the if array [mid]

FindNum: # reset the high value height = mid-1 # print the subscript of the value if you find a number, and terminate the loop elif array [mid] = = findNum: print ('find it:',array [mid],' index:',mid) break

In addition to the above methods, it can also be implemented by recursion, and the code is more concise.

Array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69 999107] # function recursive # defines a function to give three parameters: low value, high value Lookup value def BinarySearch (low,height,findNum): # calculate the median middle = (low+height) / / 2 # if the median is less than the lookup value, lock the second half if findNum > array [middle]: # reset the low number low = middle + 1 # if the median is greater than the search value, lock the first half elif findNum

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.