Question

Python: Write a program that performs a logarithmic search on an ordered list of 1000 elements. The search on the list should be on a randomly generated number between 1-1000.

Answer 1

Explanation:

• binary search is also called as Logarithmic search
• Here we first create a list with numbers from 1 to 1000 in increasing order.
• So our list contains numbers from 1 to 1000 in increasing order
• Then we will input a random number between 1 to 1000  using randint(1,1000) function
• Then we will use binary search to search for our element and its position
• Here our element and its position will be same since our list has numbers from 1 to 1000 in increasing order and random search element is between 1 and 1000

Code:

#import random package
import random

#create an empty list
l=[]

#run a for loop from 1 to 1000 and append it to the list l
for i in range(1,1001):
l.append(i)
  
#generate a random number between 1 to 1000
# here n is the element to search
n = random.randint(1,1000)

#assign 0 to first
first = 0

#assign last element index to last. Here since the length of list is 1000.
#last element index is 999
last = 999

#assign (first+last)//2 to middle
middle = (first+last)//2

#use while with condition first< = last
while (first <= last):
#if middle index element is less than n then update first with middle+1
if (l[middle] < n):
first = middle + 1

#else if middle index element is equal to n print element position and break loop
elif(l[middle] == n):
print("{0} found at position: {1}\n".format(n, middle+1))
break
# else update last with middle-1
else:
last = middle - 1;
middle = (first + last)//2
# if first index is greater than last index i means the search element is not present in the list
if (first > last):
print("Element {0} is not present in the list".format(n))

  

Sample O/P1:

522 found at position: 522

Sample O/P1:

321 found at position: 321

Sample O/P1:

639 found at position: 639

Code screenshot:

Sample O/P1 screenshot:

Sample O/P2 screenshot:

Sample O/P3 screenshot:

(If you still have any doubt please comment I will definitely help)