PYTHON

My code does not run if n = 1e8 and m = 1000 and also the number of times a number was found is always zero.

i need help modifying my code to run.

QUESTION

CODE BELOW:

import random

import time

# Function to perform linear search

def linear_search(arr, x):

for i in range(len(arr)):

if arr[i] == x:

return True

return False

# Function to perform binary search

def binary_search(arr, x):

left = 0

right = len(arr) - 1

while left

mid = (left + right) // 2

if arr[mid] == x:

return True

elif arr[mid]

left = mid + 1

else:

right = mid - 1

return False

# Generate n random integers and sort them

n = int(1e8)

range_start = 1

range_end = 100

arr = sorted(random.uniform(range_start, range_end) for _ in range(n))

# Generate m random numbers and perform linear and binary search on the array

m = 1000

search_times = []

for i in range(m):

# Generate a random number to search for

x = random.uniform(range_start, range_end)

# Perform linear search and record the time taken

start_time = time.time()

linear_search(arr, x)

end_time = time.time()

linear_time = end_time - start_time

# Perform binary search and record the time taken

start_time = time.time()

binary_search(arr, x)

end_time = time.time()

binary_time = end_time - start_time

# Record the search times

search_times.append((linear_time, binary_time))

# Calculate the average search times and number of times the number was found

linear_sum = 0

binary_sum = 0

num_found = 0

for linear_time, binary_time in search_times:

linear_sum += linear_time

binary_sum += binary_time

if binary_time == 0:

num_found += 1

avg_linear_time = linear_sum / m

avg_binary_time = binary_sum / m

# Print the results

print(f"Average linear search time: {avg_linear_time:.6f}")

print(f"Average binary search time: {avg_binary_time:.6f}")

print(f"Number of times the number was found: {num_found}")

1. Randomly generates n integer numbers (to avoid duplicates, we want the range of the data be much greater than the size of the data) and save them in an array data structure 2. Sort these numbers in order 3. Randomly generate m numbers, for each number, perform the following two search algorithms on the array, record the actual search time (either target is found, or not). 3.1 linear search algorithm 3.2 binary search algorithm 4. create a report that has the following format