Python Program to perform binary search

0 like 0 dislike
2.1k views
Python Program to perform binary search

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

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:

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 Code

def binarySearch(arr,beg,end,item):

if end >= beg:

mid = int((beg+end)/2)

if arr[mid] == item :

return mid+1

elif arr[mid] < item :

return binarySearch(arr,mid+1,end,item)

else:

return binarySearch(arr,beg,mid-1,item)

return -1

a=input("Enter elements :")

b=a.split(",")

arr=[]

for i in b:

arr.append(int(i))

arr.sort()

print("Sorted list:",arr)

item = int(input("Enter the item which you want to search:"))

location = -1;

location = binarySearch(arr,0,len(arr),item);

if location != -1:

print("Item found at location: %d" %(location))

else:

Output

Enter elements :4,26,87,12,0,67,69,34,32,48
Sorted list: [0, 4, 12, 26, 32, 34, 48, 67, 69, 87]
Enter the item which you want to search:34
Item found at location: 6