Lab Report On Linear
Search
Problem:
We are given a list of N elements.
We are also given a target.
We have to find out whether the target exists in the
list or not.
Algorithm to solve this problem:
Linear Search.
Why we use that algorithm:
To find an element from a list. The list can be sorted
or unsorted.
Basic Workflow of the Linear Search Algorithm:
Start from the first element in the list.
Compare the current element with the target.
If the current element matches the target, output
the index and stop the search.
If the target is not found after examining all
elements, output "not found."
What is the input of that algorithm?
Array/List
Key
What is the output of that algorithm?
Statement declaring the item is found or not.
True/False.
Complexity of that algorithm in Big O notation :
O(N)
Example of Best Case, Avg Case, Worst Case ( If
applicable):
Example of Best Case: Array = {1, 3, 4, 5, 7, 9, 10}, Target = 5.
Output: Yes, index
Example of Avg Case: Array = {1, 3, 4, 5, 7, 9, 10}, Target = 9.
Output: Yes
Example of Worst Case: Array = {1, 3, 4, 5, 7, 9, 10}, Target = 6.
Output: No
Example of Worst Case: Array ={ 1, 3, 4, 5, 7, 9, 10},Target = 10.
Output: Yes
Code:
#include <iostream>
using namespace std;
int LinearSearch(int A[], int N, int Key) {
for (int i = 0; i < N; i++) {
if (A[i] == Key) {
cout << "The item " << Key << " is found at index " << i
<< ".\n";
return i;
}
}
cout << "The item " << Key << " is not found.\n";
return -1;
}
int main() {
int A[] = {1, 3, 4, 5, 7, 9, 10};
int N = sizeof(A) / sizeof(A[0]);
LinearSearch(A, N, 5);
LinearSearch(A, N, 6);
LinearSearch(A, N, 10);
return 0;
}
Input:
Array = {1, 3, 4, 5, 7, 9, 10}, Targets = 5, 6, 10
Output:
