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: 4
Demonstration and Development of a Program in Python for Linear
Search in an Array
Objectives:
➢ Understand the concept of linear search in an array.
➢ Develop a Python program to perform linear search.
➢ Demonstrate how to find an element by checking each value in the array.
➢ Show how to return the position of the target element if found.
➢ Analyze the time complexity of the algorithm (O(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 the programs.
➢ Open python.
➢ Create a new file with the extension .py.
➢ Write all the required code and then run the module.
Linear Search:
Linear search is a straightforward search algorithm. In this type of search, a sequential search is
made over all items individually. Every item is checked and if a match is found then that item is
returned, otherwise the search continues till the end of the data collection. Linear search
(Searching algorithm) is used to see whether a given number is present in an array and if it is
present then at what location it occurs. It is also known as sequential search. It is straightforward
2
and works as follows: We keep on comparing each element with the element to search until it is
found or the list ends.
Concept of Linear Search:
Consider the below array of elements. Let's understand the following steps to find the element
key = 7 in the given list.
Initial Array:
Step - 1: Start the search from the first element and Check key = 7 with each element of list x.
1 3 5 4 7 9
Step - 2: If element is found, return the index position of the key.
1 3 5 4 7 9
K≠7
1 3 5 4 7 9
K≠7
1 3 5 4 7 9
K≠7
1 3 5 4 7 9
K≠7
1 3 5 4 7 9
K=7
Step 3: The element is found and it is present on index 4 and position 5.
3
Linear Search Algorithm:
➢ Start from the leftmost element of given arr[] and one by one compare element x with
each element of arr[].
➢ If x matches with any of the elements, return the index value.
➢ If x doesn’t match with any of the elements in arr[] , return -1 or element not found.
Method: 1
def search(list,key):
for i in range(len(list)):
if key==list[i]:
print("key element is found on index",i)
break
else:
print("Not found")
list=[1,2,3,4,5,6,7,8,9,10]
key=int(input("enter the key element"))
search(list,key)
Output:
Method: 2
def linear_aearch(array,n,x):
for i in range(0,n):
if (array[i]==x):
return i
return -1
array=[2,4,0,1,9]
x=9
n=len(array)
4
result=linear_aearch(array,n,x)
if (result == -1):
print("element not found")
else:
print("element found at index",result)
Output:
Method: 3
Searching using While loop:
def search(lst, n):
i = 0
while i < len(lst):
if lst[i] == n:
return True
i += 1
return False
lst = [1, 2, 3, 5, 6, 7, 8, 9, 4]
n = 0
if search(lst, n):
print("found")
else:
print("not found")
Output:
5
Finding index using while loop:
Globals () function in Python returns the dictionary of the current global symbol table. Variables
that are created outside of a function (as in all of the examples above) are known as global
variables. Global variables can be used by everyone, both inside of functions and outside.
Syntex: globals()
Parameters: No parameters required.
pos = -1
def search(lst, n):
i = 0
while i < len(lst):
if lst[i] == n:
globals()['pos'] = i # Store the position
of the found element
return True
i += 1
return False
lst = [1, 2, 3, 5, 6, 7, 8, 9, 4]
n = 6
if search(lst, n):
print("found at", pos + 1) # Output the 1-based
position
else:
print("not found")
Output:
6
Linear Search for Strings
def linearsearch(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']
x = 't'
print("element found at index " + str(linearsearch(arr,
x)))
Output:
7
Lab Tasks:
1. Write a Python program to generate the following output for linear search.
def linear_search(arr, search_element):
for i in range(len(arr)):
if arr[i] == search_element:
return i
return -1
n = int(input("How many elements?"))
arr = []
print("Enter array elements:")
for i in range(n):
element = int(input())
arr.append(element)
search_element = int(input("Enter element to search:"))
result = linear_search(arr, search_element)
if result != -1:
print("Element found at position ",result+1)
else:
print("Element not found")
Output:
8
2. Write Python program to find a maximum element of an array with its index and generate
the following output.
def find_max_element(arr):
max_element = arr[0]
max_index = 0
for i in range(1, len(arr)):
if arr[i] > max_element:
max_element = arr[i]
max_index = i
return max_element, max_index
n = int(input("Enter Number of Elements in Array: "))
arr = []
print("Enter", n, "numbers")
for i in range(n):
arr.append(int(input()))
max_element, max_index = find_max_element(arr)
print("Maximum Element:", max_element, "at index:",
max_index)
Output:
9
3. Write a Python program to find the minimum element of an array using linear search.
def find_min_element(arr):
min_element = arr[0]
min_index = 0
for i in range(1, len(arr)):
if arr[i] < min_element:
min_element = arr[i]
min_index = i
return min_element, min_index
n = int(input("Enter Number of Elements in Array: "))
arr = []
print("Enter", n, "numbers")
for i in range(n):
arr.append(int(input()))
min_element, min_index = find_min_element(arr)
print("Minimum Element:", min_element, "at index:",
min_index)
Output:
10
4. Write a Python program to print the element of the array and generate the following
output.
def print_array_elements(arr):
print("Array Content:")
for i in range(len(arr)):
print(arr[i], end=" ")
n = int(input("Enter Number of elements: "))
arr = []
print("Enter", n, "Integers")
for i in range(n):
arr.append(int(input()))
print_array_elements(arr)
Output:
11
5. Write a Python program to print the element of the array and generate the following
output.
def linear_search(arr, key):
indices = []
for i in range(len(arr)):
if arr[i] == key:
indices.append(i)
return indices
arr = [10, 20, 30, 20, 40, 50]
print(arr)
key = int(input("Enter the key element: "))
indices = linear_search(arr, key)
print("Key element is found at index:")
for index in indices:
print(index)
Output:
