Python: Write an iterative version of the following code. from random import ran
ID: 3669242 • Letter: P
Question
Python: Write an iterative version of the following code.
from random import randint
def linear_search(numbers, nbr):
"""
Returns -1 if nbr belongs to numbers,
else returns k for which numbers[k] == nbr.
Items in the list numbers must be sorted
in increasing order.
"""
for i in range(len(numbers)):
if numbers[i] == nbr:
return i
elif numbers[i] > nbr:
return -1
return -1
def binary_search(numbers, nbr):
"""
Returns True if nbr is in the sorted numbers.
Otherwise False is returned.
"""
if len(numbers) == 0:
return False
elif len(numbers) == 1:
return numbers[0] == nbr
else:
middle = len(numbers)//2
if numbers[middle] == nbr:
return True
elif numbers[middle] > nbr:
return binary_search(numbers[:middle], nbr)
else:
return binary_search(numbers[middle+1:], nbr)
def binary_trace(numbers, nbr, k):
"""
Traces binary search to check if
nbr is in the sorted list numbers.
Returns True if nbr is in numbers,
otherwise False is returned.
"""
outs = k*' ' + 'find ' + str(nbr)
print(outs + ' in L = ' + str(numbers))
if len(numbers) == 0:
return False
elif len(numbers) == 1:
return numbers[0] == nbr
else:
middle = len(numbers)//2
if numbers[middle] == nbr:
return True
elif numbers[middle] > nbr:
return binary_trace(numbers[:middle], nbr, k+1)
else:
return binary_trace(numbers[middle+1:], nbr, k+1)
def binary_index(numbers, nbr):
"""
Applies binary search to find the
position k of nbr in the sorted numbers.
Returns -1 if not nbr in numbers, or else
returns k for which numbers[k] == nbr.
"""
if len(numbers) == 0:
return -1
elif len(numbers) == 1:
if numbers[0] == nbr:
return 0
else:
return -1
else:
middle = len(numbers)//2
if numbers[middle] == nbr:
return middle
elif numbers[middle] > nbr:
return binary_index(numbers[:middle], nbr)
else:
k = binary_index(numbers[middle+1:], nbr)
if k == -1:
return -1
return k + middle + 1
def main():
"""
Illustration of linear and binary search
in a sorted list of numbers. Prompts the
user for the bounds of [a, b] and N because
the list will contain N numbers uniformly
distributed in [a,b].
"""
low = int(input('Give lower bound : '))
upp = int(input('Give upper bound : '))
nbn = int(input('How many numbers ? '))
nbrs = [randint(low, upp) for _ in range(nbn)]
nbrs.sort()
print('L =', nbrs)
while True:
snb = int(input('Give number to search for : '))
c = snb in nbrs
if c:
i = nbrs.index(snb)
d = binary_search(nbrs, snb)
d = binary_trace(nbrs, snb, 0)
kl = linear_search(nbrs, snb)
kb = binary_index(nbrs, snb)
if kb == -1:
print(snb, 'does not occur in L', not c, not d, kl == kb)
else:
print('L[%d] = %d = %d = %d'
% (kb, nbrs[kb], nbrs[i], nbrs[kl]), c, d)
ans = input('Search for more ? (y/n) ')
if ans != 'y':
break
main()
Explanation / Answer
# cook your code here
def binary_search(numbers, nbr): # just pass the array and target
low = 0
high = len(numbers)
while low <= high:
mid = (lo+high)//2
if a[mid] == br
position = mid
return -1
elif a[mid] < br;
high = mid+1
else:
low = mid-1
return -1
def linear_search(numbers,nbr):
pos = 0
found = False
while pos < len(numbers) and not found:
if numbers[pos] == item
found = True
else:
pos = pos+1
return found
def binary_trace(numbers, nbr, k):
"""
Traces binary search to check if
nbr is in the sorted list numbers.
Returns True if nbr is in numbers,
otherwise False is returned.
"""
outs = k*' ' + 'find ' + str(nbr)
print(outs + ' in L = ' + str(numbers))
if len(numbers) == 0:
return False
elif len(numbers) == 1:
return numbers[0] == nbr
else:
middle = len(numbers)//2
if numbers[middle] == nbr:
if numbers[middle] == nbr:
return True
elif numbers[middle] > nbr:
return binary_trace(numbers[:middle], nbr, k+1)
else:
return binary_trace(numbers[middle+1:], nbr, k+1)
def binary_index(numbers, nbr):
"""
Applies binary search to find the
position k of nbr in the sorted numbers.
Returns 1
if not nbr in numbers, or else
returns k for which numbers[k] == nbr.
"""
if len(numbers) == 0:
return 1
elif len(numbers) == 1:
if numbers[0] == nbr:
return 0
else:
return 1
else:
middle = len(numbers)//2
if numbers[middle] == nbr:
return middle
elif numbers[middle] > nbr:
return binary_index(numbers[:middle], nbr)
else:
k = binary_index(numbers[middle+1:], nbr)
if k == 1:
return 1
return k + middle + 1
def main():
"""
Illustration of linear and binary search
in a sorted list of numbers. Prompts the
user for the bounds of [a, b] and N because
the list will contain N numbers uniformly
distributed in [a,b].
"""
low = int(input('Give lower bound : '))
upp = int(input('Give upper bound : '))
nbn = int(input('How many numbers ? '))
nbrs = [randint(low, upp) for _ in range(nbn)]
nbrs.sort()
print('L =', nbrs)
while True:
snb = int(input('Give number to search for : '))
c = snb in nbrs
if c:
i = nbrs.index(snb)
d = binary_search(nbrs, snb)
d = binary_trace(nbrs, snb, 0)
kl = linear_search(nbrs, snb)
kb = binary_index(nbrs, snb)
if kb == 1:
print(snb, 'does not occur in L', not c, not d, kl == kb)
else:
print('L[%d] = %d = %d = %d' % (kb, nbrs[kb], nbrs[i], nbrs[kl]), c, d)
ans = input('Search for more ? (y/n) ')
if ans != 'y':
main()
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.