# Implementation of Binary Search

0 like 0 dislike
256 views

recategorized
Write a python program to Implement of Binary Search

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited

## Ques.Write a python program to Implement of Binary Search

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

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

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.  