Since the binary search was written in the algorithm class, it was implemented in Python3. Since the array below is destroyed (erasing elements), it is better to copy the data and execute it when actually using it, or change the conditions using variables such as left and right. so. I thought it would be more convenient to make it a function, but Python can be searched using in, and I just coded it in the practice of the algorithm, so it's done well, yes.
Prepare an appropriate list and sort it in ascending order. Store the number you want to find in sa_num. Use cnt to count how many times it has been processed during the search. end is used as an end condition and suc is used as a flag for success. Repeat if end is 0 If the element is 1, it is finished if only that element is examined, so flag it as end = 1. If not, get the median. If the median and the value you want to find do not match, compare the size of the median and the value you want to find. If the median is larger, the value you want to find is from 0 to index, so you don't need the right side of the array (from index to the end), so delete it using a slice. On the contrary, if it is smaller than the median, the left side is deleted. If the number of elements in the array becomes 1, take out the elements and compare them with the numerical value you want to find. If you can't find the number you're looking for, you're done.
lis = [15,23,25,601,65,87,9,103,15,30,11,13]
lis.sort()
sa_num = 25
cnt = 0
end = 0
suc = 0
while end == 0:
cnt += 1
print(lis)
if len(lis) != 1:
index = int(len(lis) / 2)
if lis[index] == sa_num:
print('suc' + str(sa_num))
end = 1
elif lis[index] > sa_num:
del lis[index:]
elif lis[index] < sa_num:
del lis[0:index]
else:
if lis[0] == sa_num:
print(sa_num)
end = 1
else:
print('Could not be located.')
suc = 1
end = 1
if suc != 1:
print(str(cnt) + 'Found in the second search.')
else:
print(str(cnt) + 'I searched several times but could not find it.')
Recommended Posts