Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. A search algorithm is primarily used to retrieve information stored or calculated within a data search request. Based on the type of search operation, these algorithms are generally classified into two categories:
- Sequential Search
- Interval Search
· Sequential Search — In a sequential search, every element in a list is checked until the requested search item is found.
· Interval Search — Interval algorithms are more efficient than sequential search algorithms and breaks an array into smaller parts to be searched. However, for an interval search to be the most effective, the data needs to be sorted before searching.
Scenario
You are working on a project which requires you to search a small array for a specific piece of data. In this lab, you will implement a Linear Search and a Binary Search.
Objectives:
After completing this lab, you will be able to:
- Implement a Linear Search in Python.
- Implement a Binary Search in Python.
Exercise 1:
Scenario
In this exercise, you will implement a Linear Search.
Task 1: Creating an Insertion Sort
- On the Jupyter Index page, click File > New Notebook > Python 3.
- Copy the following code into the notebook
def search_linear(array, target):
for i in range (len(array)):
if (array[i] == target):
return i
return None
target = 5
array = [1, 0, 4, 2, 3, 5]
result = search_linear(array, target)
if result is not None:
print(‘Value {} found at position {} using linear search’.format(target, result+1))
else: print(‘Not found’)
- To run the code, click Run.
- View the results.
- At what position was the target value found?
Task 2: Search for a different target value
- The seventh line of code reads target = 5
- Change the target value from 5 to 8
- To run the code, click Run.
- View the results.
- Was the target value found?
Exercise 2:
In this exercise, you will implement a Binary Search.
Task 1: Creating an Insertion Sort
- On the Jupyter Index page, click File > New Notebook > Python 3.
- Copy the following code into the notebook
def search_binary(sorted_array, target):
left = 0
right = len(sorted_array) — 1
while left <= right:
midpoint = left + (right — left) // 2
current = sorted_array[midpoint]
if current == target:
return midpoint
else:
if target < current:
right = midpoint — 1
else:
left = midpoint + 1
return None
target = 5
sorted_array = [0, 1, 2, 3, 4, 5]
result = search_binary(sorted_array, target)
if result is not None:
print(‘Value {} found at position {} using binary search’.format(target, result+1))
else:
print(‘Not found’)
- To run the code, click Run.
- View the results.
- At what position was the target value found?
Task 2: short description of task
- The 16th line of code reads target = 5
- Change the target value from 5 to 8
- To run the code, click Run.
- View the results.
- Was the target value found?
