Question

in python

1. Generates 50,000 random numbers and puts them in an array.
2. Sorts the numbers using any sorting technique (Selection sort is fine, but you can try another one). This should take a few minutes to run.
3. Ask the user for a number between 0 and 20,000,000 and search for it in your sorted array using a simple linear search. Is this a good idea?
4. Ask the user for a number between 0 and 20,000,000 and search for it in your sorted array using a binary search.

Answer 1

Linear search algorithms worst time complexity is of order N where N is the size of the array, while binary search algorithm worst time complexity is log(N), for higher number of N log(N) < N, which means time taken to find a number using binary search is far less than searching the element using linear search.

Note: binary search can only be done on sorted array, if the array is not sorted we have to do linear search only.

=========================
Below is the python code.
=========================
===============================================================================

import random


# Sorts the numbers using any sorting technique (Selection sort is fine, but you can try another one). This should take a few minutes to run.
def selection_sort(num_list):
    for i in range(len(num_list)):
        min_index = i
        for j in range(i + 1, len(num_list)):
            if num_list[min_index] > num_list[j]:
                min_index = j
        num_list[i], num_list[min_index] = num_list[min_index], num_list[i]


# Generates 50,000 random numbers and puts them in an array.
random_num_list = []
for _ in range(50000):
    random_num_list.append(random.randint(0, 20000000))
print('Random numbers generated..')
# sorting the numbers using selection sort
print('Sorting the random numbers..')
selection_sort(random_num_list)

print(random_num_list)

# Ask the user for a number between 0 and 20,000,000 and
# search for it in your sorted array using a simple linear search.
# Is this a good idea?
search_num = int(input('Enter a number between 0 and 20,000,000: '))

print('Searching a number using simple linear search on a sorted list....')
for i in range(len(random_num_list)):
    if random_num_list[i] == search_num:
        print('Number found at index: {}'.format(i))
        break
if not (i < len(random_num_list)):
    print('Number not found.')

print('Searching a number using binary search on a sorted list..')
search_num = int(input('Enter a number between 0 and 20,000,000: '))
left = 0
right = len(random_num_list)
flag=True
while left < right:
    mid = (right+left) // 2
    if random_num_list[mid] == search_num:
        print('Number found at index: {}'.format(mid))
        flag=False
        break
    elif random_num_list[mid] < search_num:
        left = mid + 1
    else:
        right = mid
if flag:
    print('Number not found.')