#include <stdio.h>
// Linear search - search for element in unsorted array
// Check if each element is equal to the target one by one until target is reached
int linearSearch(int *arr, int target, int len, int tshow) {
int numOfOperations = 0;
for (int x = 0; x < len; x++) {
numOfOperations++;
if (arr[x] == target) {
if (tshow) {
printf("Size of data: %d, num of operations (worst-case): %d.\n", len, numOfOperations);
}
return x;
}
}
if (tshow) {
printf("Size of data: %d, num of operations (worst-case): %d.\n", len, numOfOperations);
}
return -1;
}
int main(int argc, char* argv[]) {
int array[] = {5, 2, 7, 15, 31, 98, 26, 59, 44};
int num = 31;
int idx = linearSearch(array, num, sizeof(array)/sizeof(*array), 0);
if (idx == -1) {
printf("Value not found.\n");
} else {
printf("%d found at index %d.\n", num, idx);
}
num = 44;
idx = linearSearch(array, num, sizeof(array)/sizeof(*array), 1);
// Size of data: 9, num of operations (worst-case): 9.
// 9 = 9
// Time complexity: O(n)
}
int array[] = {5, 2, 7, 15, 31, 98, 26, 59, 44};
int num = 31;
Initialize the array and the value (number) to be searched for.
int idx = linearSearch(array, num, sizeof(array)/sizeof(*array), 0);
The linearSearch function takes the array, the value to be searched for and the length of the array and returns the index of the element where the value is stored in the array, the index is stored in the variable, idx.
if (idx == -1) {
printf("Value not found.\n");
} else {
printf("%d found at index %d.\n", num, idx);
}
If idx is equal to -1, the linearSearch function returned -1, meaning the number is not in the array.
Since -1 is not an index number, "Value not found." is printed instead.
If idx is any number other than -1, the linearSearch successfully returned the index value of the number and the index can be printed.
num = 44; idx = linearSearch(array, num, sizeof(array)/sizeof(*array), 1);
Test linearSearch with last element to see worst-case number of operations. Pass 1 as final argument instead of 0.
int linearSearch(int *arr, int target, int len, int tshow) {
The linearSearch function takes array, target element (value to be found), length of array and tshow - whether to display number of operations or not.
In the main function, array was passed as the argument arr (int*) of the linearSearch function. This is because array is passed as a pointer to the first element of the array (int*) rather than the array (int[]).
int numOfOperations = 0;
for (int x = 0; x < len; x++) {
numOfOperations++;
if (arr[x] == target) {
if (tshow) {
printf("Size of data: %d, num of operations (worst-case): %d.\n", len, numOfOperations);
}
return x;
}
}
In the for loop, x starts at 0 and increases each iteration until it equals len-1. x represents the index of the elements. When the value of the element in the array at x is equal to the target, the index, x is returned. If for loop ends without a return statement, the target value is not in the array.
return -1;
Return -1 if the value is not in the list (loop ended without a return statement). -1 is not a valid index and indicates that there is no index for the given value.
numOfOperations counts the number of read operations (number of times an element in the list is compared to the target). It is only displayed if tshow = 1 and the program reaches the worst-case number of operations (element doesn't exist or is at the end of the array).
Index: 0