#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) {
for (int x = 0; x < len; x++) {
if (arr[x] == target) {
return x;
}
}
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));
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));
// Size of data: 9, num of operations (worst-case): 10.
// Steps by input size: T(n) = n
// Time complexity: O(n) = 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));
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));
Test linearSearch with last element to see worst-case number of operations.
int linearSearch(int *arr, int target, int len) {
The linearSearch function takes an array, the target element (value to be found) and the length of array.
In the main function, array was passed into arr (int*) in the linearSearch function. Here, a pointer to the first element of array (type int*) is passed into the function instead of the array itself (type int[]).
for (int x = 0; x < len; x++) {
if (arr[x] == target) {
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.
Index: 0