Example:1
Write a python script to search an element with in a list using Binary Search. (Without using functions)
Sol:
def binary_search(arr, x):
beg = 0
end = len(arr) - 1
mid = 0
while(beg <= end):
mid = (beg + end) // 2
# Check if x is present at mid
if(arr[mid]==x):
return mid
else:
# If x is greater, ignore left half
if(x > arr[mid]):
beg = mid + 1
else:
# If x is smaller, ignore right half
if(x < arr[mid]):
end = mid - 1
# If we reach here, then the element was not present
return -1
#-- main --
#arr is a list containing elements
arr = [3,10,15,20,35,40,60]
# x : element to search
#x = 4
x=int(input("Enter the element to search "))
# Function call
result = binary_search(arr, x)
if result != -1:
print("Element is present at index", str(result+1))
else:
print("Element is not present in array")
Output:
case 1:
Enter the element to search 4
Element is not present in array
case 2:
Enter the element to search 20
Element is present at index 4
Example:2
Write a python script to search an element with in a list using Binary Search.(Using functions)
Sol:
#create an empty list
#global blank list
arr=[]
def create_list():
print("Enter the elements in increasing order ")
while True:
a=int(input("Enter the element to add in list "))
arr.append(a)
ch=input("Like to add more elements (y/n) ")
if(ch=="y" or ch=="Y"):
continue
else:
break
def display_list():
# 1st method to display list
print("List is ")
print(arr)
# 2nd method to display list
for i in arr:
print(i,end=' ')
def binary_search(arr, x):
beg = 0
end = len(arr) - 1
mid = 0
while(beg <= end):
mid = (beg + end) // 2
# Check if x is present at mid
if(arr[mid]==x):
return mid
else:
# If x is greater, ignore left half
if(x > arr[mid]):
beg = mid + 1
else:
# If x is smaller, ignore right half
if(x < arr[mid]):
end = mid - 1
# If we reach here, then the element was not present
return -1
#-- main --
#call function to create a list
create_list()
#display elements of list
display_list()
x=int(input("\nEnter the element to search "))
# Function call
result = binary_search(arr, x)
if result != -1:
print("Element is present at index", str(result+1))
else:
print("Element is not present in array")
Output:
case 1:
Enter the elements in increasing order
Enter the element to add in list 25
Like to add more elements (y/n) y
Enter the element to add in list 63
Like to add more elements (y/n) y
Enter the element to add in list 85
Like to add more elements (y/n) y
Enter the element to add in list 95
Like to add more elements (y/n) y
Like to add more elements (y/n) n
List is
[25, 63, 85, 95, 75]
25 63 85 95 75
Enter the element to search 95
Element is present at index 4
case :2
Enter the elements in increasing order
Enter the element to add in list 2
Like to add more elements (y/n) y
Enter the element to add in list 6
Like to add more elements (y/n) y
Enter the element to add in list 8
Like to add more elements (y/n) y
Enter the element to add in list 25
Like to add more elements (y/n) y
Enter the element to add in list 35
Like to add more elements (y/n) y
Enter the element to add in list 62
Like to add more elements (y/n) n
List is
[2, 6, 8, 25, 35, 62]
2 6 8 25 35 62
Enter the element to search 35
Element is present at index 5
