UNIVERSITYOF ENGINEERING AND TECHNOLOGY
TAXILA
Submitted To:
Engr. Iqra Jabeen
Submitted By:
Amjid Khan (23-TE-86)
Subject:
Data Structure and Algorithms Lab
DEPARTMENT OF TELECOMMUNICATION
ENGINEERING
1
Lab Report: 5
Demonstration and Implementation of a Program in Python for Binary
Search in an Array
Objectives:
➢ Understand the concept of Binary search in an array.
➢ Develop a Python program to perform Binary search.
➢ Demonstrate how to find an element by checking values in the array.
➢ Show how to return the position of the target element if found.
➢ Analyze the time complexity of the algorithm (O (log n)).
Equipment Required:
➢ Computer/Laptop with at least 4 GB RAM.
➢ Python 3.x installed and configured.
➢ IDE/Text Editor like PyCharm, VS Code, or Jupyter, Notebook etc.
➢ NumPy library (optional) for advanced array handling.
➢ Internet connection for downloading resources and accessing documentation.
Procedure:
➢ Open Computer System.
➢ Go to all programs.
➢ Open python.
➢ Create a new file with the extension .py.
➢ Write all the required code and then run the module.
Binary Search:
Binary search is an efficient algorithm used to find the position of a target value within a
sorted array or list. It works by repeatedly dividing the search interval in half. If the value of the
target is less than the value in the middle of the interval, the search continues in the lower half;
otherwise, it continues in the upper half.
2
Concept of Binary Search:
Binary search is an algorithmic approach used to locate a specific element within a sorted
array or list. It follows a divide-and-conquer strategy, repeatedly dividing the search space in half
until the desired element is found or determined to be absent. Its key advantage lies in its time
complexity, which is logarithmic — O (log n) — whereas a simple linear search would have a time
complexity of O(n) in the worst case.
Algorithmic Steps:
1. Begin with a sorted array or list: Binary search requires the input data to be sorted in
ascending or descending order. This sorted property allows the algorithm to make
informed decisions during the search process.
2. Set the lower and upper boundaries: Initially, the lower boundary is set to the first index
of the array, and the upper boundary is set to the last index.
3. Compute the middle index: Calculate the middle index of the search space by taking the
average of the lower and upper boundaries. This is done by using the formula:
lower + high
𝑚𝑖𝑑 =
2
4. Compare the middle element: Compare the element at the middle index with the desired
value. If they are equal, the element is found, and its index is returned.
5. Adjust the boundaries: If the middle element is greater than the desired value, it means
the desired element, if present, must be in the left half of the array. In this case, set the
new upper boundary to `middle — 1`. If the middle element is less than the desired value,
3
it means the desired element, if present, must be in the right half of the array. In this case,
set the new lower boundary to `middle + 1`.
6. Repeat steps 3–5: Repeat the above steps, recalculating the middle index based on the
updated boundaries, until the desired element is found or the boundaries overlap,
indicating that the element is not present in the array.
Code#1:
A = list()
n = int(input("Enter the number of elements:"))
print("Enter", n, "Elements")
for i in range(n):
A.append(int(input()))
A.sort()
print("List after sorting:")
print(A)
s = int(input("Enter search element:"))
low = 0
high = len(A) - 1
mid = 0
while low <= high:
mid = (low + high) // 2
if A[mid] == s:
print(s, "is found at position", mid + 1)
break
elif A[mid] > s:
high = mid - 1
else:
low = mid + 1
else:
print(s, "is not found")
4
Output:
Code#2:
def Binarysearch(list1, key):
low = 0
high = len(list1) - 1
found = False
while low <= high and not found:
mid = (low + high) // 2
if key == list1[mid]:
found = True
elif key > list1[mid]:
low = mid + 1
else:
high = mid - 1
if found == True:
print("key is found")
else:
print("key is not found")
list1 = [23, 1, 4, 2, 3]
list1.sort()
print(list1)
key = int(input("Enter the key: "))
Binarysearch(list1, key)
5
Output:
Code#3:
def binarysearch(L, low, high, mid, s):
if low <= high:
mid = (low + high) // 2
if L[mid] == s:
print(s, "is found at position", mid + 1)
elif L[mid] > s:
binarysearch(L, low, mid - 1, mid, s)
else:
binarysearch(L, mid + 1, high, mid, s)
else:
print(s, "is not found")
L = list()
n = int(input("Enter the number of elements to be
inserted:"))
print("Enter", n, "Elements")
for i in range(n):
L.append(int(input()))
L.sort()
print("List after sorting:")
print(L)
s = int(input("Enter search element:"))
low = 0
high = len(L) - 1
6
mid = (low + high) // 2
binarysearch(L, low, high, mid, s)
Output:
Binary search for duplicate value:
def find(A, target):
low = 0
high = len(A) - 1
while low <= high:
mid = (low + high) // 2
if A[mid] < target:
low = mid + 1
elif A[mid] > target:
high = mid - 1
else:
if mid - 1 < 0:
return mid
if A[mid - 1] != target:
return mid
high = mid - 1
return None
A = [1, 22, 33, 44, 55, 55, 67, 67, 67, 80]
7
target = 55
x = find(A, target)
print("The targeted element is found at position",x+1)
Output:
8
Lab Tasks:
1. Write python program for finding the last occurrence of element with duplicate elements using
binary search.
def binary_search(arr, target, find_first):
low, high = 0, len(arr) - 1
result = -1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
result = mid
if find_first:
high = mid - 1
else:
low = mid + 1
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
arr = [1, 2, 11, 11, 11, 19, 20]
target = 11
first_index = binary_search(arr, target,
find_first=True)
last_index = binary_search(arr, target,
find_first=False)
print(f"First occurrence of {target} = {first_index}")
print(f"Last occurrence of {target} = {last_index}")
Output:
9
2. Write a python program to find the occurrence of 1’s in sorted binary array and generate the
following output.
def count_ones(arr):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == 0:
left = mid + 1
else:
right = mid - 1
if left >= len(arr):
return 0
first_occurrence = left
left = first_occurrence
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == 0:
right = mid - 1
else:
left = mid + 1
last_occurrence = right
return last_occurrence - first_occurrence + 1
arr = [0, 0, 0, 1, 1, 1, 0, 0, 0]
target = 1
count = count_ones(arr)
print("The target 1 occurs", count, "times.")
Output:
10
3. Consider the following list and write a python program to find the
Array = [2,3,5,7,8,10,12,15,18,20]
a) Find maximum.
b) Find minimum.
c) Find summation of number.
d) Find average of numbers.
def find_max_min_sum_avg(arr):
max_num = arr[0]
min_num = arr[0]
sum_num = 0
for num in arr:
if num > max_num:
max_num = num
if num < min_num:
min_num = num
sum_num += num
avg_num = sum_num / len(arr)
return max_num, min_num, sum_num, avg_num
arr = [2, 3, 5, 7, 8, 10, 12, 15, 18, 20]
max_num, min_num, sum_num, avg_num =
find_max_min_sum_avg(arr)
print("Maximum number:", max_num)
print("Minimum number:", min_num)
print("Summation of numbers:", sum_num)
print("Average of numbers:", avg_num)
Output:
11
4. Considered the following sorted array containing duplicates, efficiently find each
element’s frequency.
Input
[1,1,1,2,2,3,3,3,5,5,6]
Output
1 and 3 occurs thrice
2 and 5 occurs twice
def find_element_frequency(arr):
frequency_dict = {}
for element in arr:
frequency_dict[element] =
frequency_dict.get(element, 0) + 1
return frequency_dict
def group_and_print(frequency_dict):
count_1 = frequency_dict.get(1, 0)
count_3 = frequency_dict.get(3, 0)
count_2 = frequency_dict.get(2, 0)
count_5 = frequency_dict.get(5, 0)
group_1_and_3 = min(count_1, 3)
group_2_and_5 = min(count_2, 2)
print(f"1 and 3 occurs {group_1_and_3} times")
print(f"2 and 5 occurs {group_2_and_5} times")
arr = [1, 1, 1, 2, 2, 3, 3, 3, 5, 5, 6]
frequency_dict = find_element_frequency(arr)
group_and_print(frequency_dict)
Output:
12
5. Write a python program to find the smallest missing element in the following array and
generate the following output.
Input
Array = [0,1,2,4,5,6,7,8,9,10]
Output
The smallest missing element is 3
def find_smallest_missing_element(arr):
if arr[0] != 0:
return 0
for i in range(1, len(arr)):
if arr[i] - arr[i - 1] > 1:
return arr[i - 1] + 1
return arr[-1] + 1
arr = [0, 1, 2, 4, 5, 6, 7, 8, 9, 10]
smallest_missing = find_smallest_missing_element(arr)
print("The smallest missing element is",
smallest_missing)
Output:
