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:
print("Item not found")
|
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 |
For more RGPV/UTMP CSE V Sem Python Lab Experiments Click here
| 
| 
