Ques.Write a python program to Implement of Binary Search
Answer :
Binary search : It is a sorting algorithm which follows divide and conquer algorithm in which, the list is divided into two parts and then each element is compared to middle element of the list. If we get a match then, position of middle element is returned otherwise, we search into either of the halves depending upon the result produced through the match.
Example :
Find 103 in {1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
- Step 1 - middle element is 19 < 103 : 1, 5 ,6 ,18 ,19 ,25, 46 ,78, 102 ,114
- Step 2 - middle element is 78 < 103 : 1 ,5 ,6, 18 ,19 ,25, 46 ,78, 102 ,114
- Step 3 - middle element is 102 < 103 : 1, 5, 6, 18, 19 ,25, 46, 78, 102, 114
- Step 4 - middle element is 114 > 103 : 1 ,5 ,6, 18, 19, 25, 46 ,78 ,102, 114
- Step 5 - searched value is absent : 1 , 5 , 6 ,18 ,19 , 25 , 46 , 78 , 102 , 114
Algorithm :
Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then
return l
else
m := ⌊(l + r) / 2⌋
if x ≤ numbers[m] then
return Binary-Search(numbers[], x, l, m)
else
return Binary-Search(numbers[], x, m+1, r)
Program :
|
def binary_sort(sorted_list, length, key):
start = 0
end = length-1
while start <= end:
mid = int((start + end)/2)
if key == sorted_list[mid]:
print("\nEntered number %d is present at position: %d" % (key, mid))
return -1
elif key < sorted_list[mid]:
end = mid - 1
elif key > sorted_list[mid]:
start = mid + 1
print("\nElement not found!")
return -1
lst = []
size = int(input("Enter length of list: \t"))
for n in range(size):
numbers = int(input("Enter any number: \t"))
lst.append(numbers)
lst.sort()
print('\n\nsorted list is:', lst)
x = int(input("\nEnter the number to search: "))
binary_sort(lst, size, x)
|
Output :
Enter length of list: 5
Enter any number: 12
Enter any number: 122
Enter any number: 23
Enter any number: 22
Enter any number: 45
sorted list is: [12, 22, 23, 45, 122]
Enter the number to search: 23
Entered number 23 is present at position: 2
For more Rajasthan Technical University CSE-III Sem DSA Lab Experiments CLICK HERE
| 
| 
