In some cases, the data area of a problem is an ordered interval. Dichotomy is used to divide the interval into two subintervals and then determine if the process of computation is in the left subinterval or the right subinterval. If the solution isn’t obtained, then repeat the above steps. For a problem whose time complexity is O(n), if dichotomy can be used to solve it, its time complexity can be improved to O(log2(n)).
Dichotomy is used in many algorithms, such as binary search, recursive halving method, quick sort, merge sort, binary search tree, and segment tree. Among these methods, binary search and recursive halving method are relatively simple algorithms.
The idea for binary search is as follows: Suppose the data area is an interval in ascending order. The search begins by comparing x with the number in the middle of the interval. If x equals this number, the search terminates. If x is smaller than the number, then we need only search in the left half; if x is greater than the number, then we need only search in the right half. We repeat the above steps until the search ends.
How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We’re assuming that the cards must be perpendicular to the table.) With two cards, you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general, you can make n cards overhang by 1/2 + 1/3 + 1/4 + … + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs the third by 1/3, the third overhangs the fourth by 1/4, and so on, and the bottom card overhangs the table by 1/(n + 1).
import math
numbertofind = input("Enter the number you want to find. Type exit to exit. ")
a = 2
b = 1/a
thesum = 0
alist = []
while thesum <= 5.20:
thesum += b
alist.append((thesum, a))
a += 1
b = 1/a
def findnumber (hangovernumber, alist):
index1 = 275
index2 = 0
while True:
if alist[math.floor((index1+index2)/2)][0] > hangovernumber:
index1 = math.floor((index1 + index2)/2)
if index2 == index1:
return index1
elif alist[math.floor((index1+index2)/2)][0] < hangovernumber:
index2 = math.ceil((index1 + index2)/2)
if index2 == index1:
return index1
else:
return index1
while str(numbertofind) != "exit":
print(alist[findnumber(float(numbertofind), alist)][1] - 2)
numbertofind = input("Enter the number you want to find. Type exit to exit. ")
You need login to submit your solution
You need login to comment