Given a list of integers sorted or unsorted your task is to sort the list in ascending order. also given that key, check if the key is part of the list of integers or not.
Using Binary search.
Binary search is a technique that takes input as a sorted list of numbers and a key.
1) Calculate the middle index and check if the middle index is equal to the key. if so , the key is found in the middle of the list.
2) Else checks if the middle element is greater than the key then it compares the key with the right side off the list. By setting start index as middle
3) Else if the middle element is less than the key element then it compares the key with the the left side of the list. By setting the end index as middle.
Until the start index is less than the end index.
Write A Python Function To Demonstrate The Binary Search Operation
In the below program let's take a sorted list directly into the program by assigning the list variable to the sorted list of numbers.
Define a function binary_search() passing input argument as list of numbers and a key. Set the start to zero and end index to length of list.
def binary_search(my_list, key):
start = 0
end = len(my_list) - 1
Using while loop until start is less than or equal to end index. Calculate the middle index by averaging out the start and end index.
Using if statement compare the key with the middle item if true return the index.
while start <= end:
middle = (start + end) // 2
if my_list[middle] == key:
return f'{key} found at index {middle}'
Else if the middle item is greater than the key then search the remaining right side of the list. By setting start to middle
elif my_list[middle] > key:
end = middle - 1
Else if the middle item is lesser than the key then search the remaining left side of the list. By setting end to middle
elif my_list[middle] < key:
start = middle + 1
If the while loop completes, return the item not found message.
return f'{key} not found in the list'
In the main program take an integer list and assign the random value to make sure you have sorted the list of integers during the assignment.
Use the print statement to directly call the binary search by passing the argument as a list of integers and key variables. in the below function the key variable is 14.
integer_list = [11, 14, 23, 41, 48, 51, 67, 77, 79]
print(binary_search(integer_list, 14))
Complete program
=====================
def binary_search(my_list, key):
start = 0
end = len(my_list) - 1
while start <= end:
middle = (start + end) // 2
if my_list[middle] == key:
return f'{key} found at index {middle}'
elif my_list[middle] > key:
end = middle - 1
elif my_list[middle] < key:
start = middle + 1
return f'{key} not found in the list'
integer_list = [11, 14, 23, 41, 48, 51, 67, 77, 79]
print(binary_search(integer_list, 14))
Output 1
===================
14 found at index 1
Output 2 for print(binary_search(integer_list, 100))
===================
100 not found in the list
Output 3 for print(binary_search(integer_list, 10))
===================
10 not found in the list
Get the list of integers and search element as input from the user
Copy the above program and there is a slight change in the below program. We are asking a user to enter the list of integers in the main program then using the sorted function call sorting the list of integers and again asking a user to enter the search element that is key.
Then calling the function binary_search() as shown below.
Complete Program
===================
def binary_search(my_list, key):
start = 0
end = len(my_list) - 1
while start <= end:
middle = (start + end) // 2
if my_list[middle] == key:
return f'{key} found at index {middle}'
elif my_list[middle] > key:
end = middle - 1
elif my_list[middle] < key:
start = middle + 1
return f'{key} not found in the list'
n = int(input("Enter List Size : "))
integer_list = []
for _ in range(n):
item = int(input("Enter List Item : "))
integer_list.append(item)
integer_list = sorted(integer_list)
number = int(input("Enter a Number to Search : "))
print(binary_search(integer_list, number))
OUTPUT
=============
Enter List Size : 5
Enter List Item : 32
Enter List Item : 2
Enter List Item : 44
Enter List Item : 67
Enter List Item : 1
Enter a Number to Search : 23
23 not found in the list
OUTPUT
===================
Enter List Size : 10
Enter List Item : 9
Enter List Item : 6
Enter List Item : 4
Enter List Item : 23
Enter List Item : 90
Enter List Item : 12
Enter List Item : 45
Enter List Item : 12
Enter List Item : 33
Enter List Item : 22
Enter a Number to Search : 12
12 found at index 4
Conclusion
=============
The above program contains only three logic: calculate middle index, check if key is equal to middle index if yes return the index.
Check if the middle item is greater than the key then search the item on the right side.
Check if the middle item is less than the key then search the item on the left side of the list.
0 Comments