JAIDEV EDUCATION SOCIETY’S
J D COLLEGE OF ENGINEERING AND MANAGEMENT
KATOL ROAD, NAGPUR
Website: www.jdcoem.ac.in E-mail:
[email protected] (An Autonomous Institute, with NAAC "A" Grade)
Affiliated to DBATU, RTMNU & MSBTE Mumbai
Department of Artificial Intelligence
“A Place to Learn, A Chance to Grow”
Session: 2024-25
VISION MISSION
1. To create self-learning environment by facilitating leadership qualities, team spirit and
ethical responsibilities.
To be recognized for excellent engineering, developing global leaders both
in educational and research in the domain of computer science and wireless 2. To improve department-industry collaboration, interaction with professional society
engineering. through technical knowledge and internship program.
3. To promote research and development with current techniques through well qualified
resources in the area of computer science and wireless engineering.
Experiment No. 04
Aim: Write a python program for Linear Search and Binary search.
Software Requirement: Python IDE, PyCharm, Visual Studio Code (VS Code),
Jupyter Notebook.
Theory:
Searching: Searching is just finding out the data item among given list. Two cases are possible
that either item is found or item not present in the list. The Searching is divided into two types.
1) Linear Search
2) Binary Search
Linear search:
Linear Search is a very simple search algorithm. In this sequential search is done by searching
items one by one. Each item is checked and if a match is found then that particular item is
returned, otherwise the search is continuing till end of the list of items. If item which is to be
searched is not present in list, then the search is called as unsuccessful search. Linear search is
also known as sequential search.
Algorithm for Linear Search Algorithm:
The algorithm for linear search can be broken down into the following steps:
Start: Begin at the first element of the collection of elements.
Compare: Compare the current element with the desired element.
Found: If the current element is equal to the desired element, return true or index to
the current element.
Move: Otherwise, move to the next element in the collection.
Repeat: Repeat steps 2-4 until we have reached the end of collection.
Not found: If the end of the collection is reached without finding the desired element,
return that the desired element is not in the array.
JAIDEV EDUCATION SOCIETY’S
J D COLLEGE OF ENGINEERING AND MANAGEMENT
KATOL ROAD, NAGPUR
Website: www.jdcoem.ac.in E-mail: [email protected]
(An Autonomous Institute, with NAAC "A" Grade)
Affiliated to DBATU, RTMNU & MSBTE Mumbai
Department of Artificial Intelligence
“A Place to Learn, A Chance to Grow”
Session: 2024-25
VISION MISSION
1. To create self-learning environment by facilitating leadership qualities, team spirit and
ethical responsibilities.
To be recognized for excellent engineering, developing global leaders both
in educational and research in the domain of computer science and wireless 2. To improve department-industry collaboration, interaction with professional society
engineering. through technical knowledge and internship program.
3. To promote research and development with current techniques through well qualified
resources in the area of computer science and wireless engineering.
For example: Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30
Step 1: Start from the first element (index 0) and compare key with each element (arr[i]).
Comparing key with first element arr[0]. SInce not equal, the iterator moves to the next
element as a potential match.
Comparing key with next element arr[1]. Since not equal, the iterator moves to the next
element as a potential match.
Step 2: Now when comparing arr[2] with key, the value matches. So the Linear Search
Algorithm will yield a successful message and return the index of the element when key is
found (here 2).
JAIDEV EDUCATION SOCIETY’S
J D COLLEGE OF ENGINEERING AND MANAGEMENT
KATOL ROAD, NAGPUR
Website: www.jdcoem.ac.in E-mail: [email protected]
(An Autonomous Institute, with NAAC "A" Grade)
Affiliated to DBATU, RTMNU & MSBTE Mumbai
Department of Artificial Intelligence
“A Place to Learn, A Chance to Grow”
Session: 2024-25
VISION MISSION
1. To create self-learning environment by facilitating leadership qualities, team spirit and
ethical responsibilities.
To be recognized for excellent engineering, developing global leaders both
in educational and research in the domain of computer science and wireless 2. To improve department-industry collaboration, interaction with professional society
engineering. through technical knowledge and internship program.
3. To promote research and development with current techniques through well qualified
resources in the area of computer science and wireless engineering.
Advantages of Linear Search Algorithm:
Linear search can be used irrespective of whether the array is sorted or not. It can be
used on arrays of any data type.
Does not require any additional memory.
It is a well-suited algorithm for small datasets.
Disadvantages of Linear Search Algorithm:
Linear search has a time complexity of O(N), which in turn makes it slow for large
datasets.
Not suitable for large arrays.
Binary Search:
Binary search is a search algorithm used to find the position of a target value within a sorted
array. It works by repeatedly dividing the search interval in half until the target value is found
or the interval is empty. The search interval is halved by comparing the target element with the
middle value of the search space.
Binary Search Algorithm:
Below is the step-by-step algorithm for Binary Search:
Divide the search space into two halves by finding the middle index “mid”.
Compare the middle element of the search space with the key.
JAIDEV EDUCATION SOCIETY’S
J D COLLEGE OF ENGINEERING AND MANAGEMENT
KATOL ROAD, NAGPUR
Website: www.jdcoem.ac.in E-mail:
[email protected] (An Autonomous Institute, with NAAC "A" Grade)
Affiliated to DBATU, RTMNU & MSBTE Mumbai
Department of Artificial Intelligence
“A Place to Learn, A Chance to Grow”
Session: 2024-25
VISION MISSION
1. To create self-learning environment by facilitating leadership qualities, team spirit and
ethical responsibilities.
To be recognized for excellent engineering, developing global leaders both
in educational and research in the domain of computer science and wireless 2. To improve department-industry collaboration, interaction with professional society
engineering. through technical knowledge and internship program.
3. To promote research and development with current techniques through well qualified
resources in the area of computer science and wireless engineering.
If the key is found at middle element, the process is terminated.
If the key is not found at middle element, choose which half will be used as the next
search space.
o If the key is smaller than the middle element, then the left side is used for next
search.
o If the key is larger than the middle element, then the right side is used for next
search.
This process is continued until the key is found or the total search space is exhausted.
Example:
Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.
JAIDEV EDUCATION SOCIETY’S
J D COLLEGE OF ENGINEERING AND MANAGEMENT
KATOL ROAD, NAGPUR
Website: www.jdcoem.ac.in E-mail: [email protected]
(An Autonomous Institute, with NAAC "A" Grade)
Affiliated to DBATU, RTMNU & MSBTE Mumbai
Department of Artificial Intelligence
“A Place to Learn, A Chance to Grow”
Session: 2024-25
VISION MISSION
1. To create self-learning environment by facilitating leadership qualities, team spirit and
ethical responsibilities.
To be recognized for excellent engineering, developing global leaders both
in educational and research in the domain of computer science and wireless 2. To improve department-industry collaboration, interaction with professional society
engineering. through technical knowledge and internship program.
3. To promote research and development with current techniques through well qualified
resources in the area of computer science and wireless engineering.
Advantages of Binary Search:
Binary search is faster than linear search, especially for large arrays.
More efficient than other searching algorithms with a similar time complexity, such as
interpolation search or exponential search.
Binary search is well-suited for searching large datasets that are stored in external
memory, such as on a hard drive or in the cloud.
Disadvantages of Binary Search:
The array should be sorted.
JAIDEV EDUCATION SOCIETY’S
J D COLLEGE OF ENGINEERING AND MANAGEMENT
KATOL ROAD, NAGPUR
Website: www.jdcoem.ac.in E-mail:
[email protected] (An Autonomous Institute, with NAAC "A" Grade)
Affiliated to DBATU, RTMNU & MSBTE Mumbai
Department of Artificial Intelligence
“A Place to Learn, A Chance to Grow”
Session: 2024-25
VISION MISSION
1. To create self-learning environment by facilitating leadership qualities, team spirit and
ethical responsibilities.
To be recognized for excellent engineering, developing global leaders both
in educational and research in the domain of computer science and wireless 2. To improve department-industry collaboration, interaction with professional society
engineering. through technical knowledge and internship program.
3. To promote research and development with current techniques through well qualified
resources in the area of computer science and wireless engineering.
Binary search requires that the data structure being searched be stored in contiguous
memory locations.
Binary search requires that the elements of the array be comparable, meaning that
they must be able to be ordered.
Program:
For Linear Search:
def linear_Search(list1, n, key):
# Searching list1 sequentially
for i in range(0, n):
if (list1[i] == key):
return i
return -1
list1 = [1 ,3, 5, 4, 7, 9]
key = 7
n = len(list1)
res = linear_Search(list1, n, key)
if(res == -1):
print("Element not found")
else:
print("Element found at index: ", res)
OUTPUT:
Element found at index: 4
For Binary Search:
def binary_search(list1, n):
low = 0
high = len(list1) - 1
while low <= high:
mid = (high + low) // 2
JAIDEV EDUCATION SOCIETY’S
J D COLLEGE OF ENGINEERING AND MANAGEMENT
KATOL ROAD, NAGPUR
Website: www.jdcoem.ac.in E-mail:
[email protected] (An Autonomous Institute, with NAAC "A" Grade)
Affiliated to DBATU, RTMNU & MSBTE Mumbai
Department of Artificial Intelligence
“A Place to Learn, A Chance to Grow”
Session: 2024-25
VISION MISSION
1. To create self-learning environment by facilitating leadership qualities, team spirit and
ethical responsibilities.
To be recognized for excellent engineering, developing global leaders both
in educational and research in the domain of computer science and wireless 2. To improve department-industry collaboration, interaction with professional society
engineering. through technical knowledge and internship program.
3. To promote research and development with current techniques through well qualified
resources in the area of computer science and wireless engineering.
# Check if n is present at mid
if list1[mid] < n:
low = mid + 1
# If n is greater, compare to the right of mid
elif list1[mid] > n:
high = mid - 1
# If n is smaller, compared to the left of mid
else:
return mid
# element was not present in the list, return -1
return -1
# Initial list1
list1 = [12, 24, 32, 39, 45, 50, 54]
n = 45
# Function call
result = binary_search(list1, n)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in list1")
OUTPUT:
Element is present at index 4
Conclusion:
Hence, thus I have executed the Python program to perform Linear Search and Binary Search
Successfully.
