NMKN Studio

This time around we’re looking at the linear search algorithm and how to implement it in C++. It’s a very simple algorithm that’ll iterate down the entire list of entries to find the one we’re interested in. It’s pretty much a brute force approach but it’s the first one most people learn when they dive deep into algorithms, so let’s have a look at it.

#include <iostream>
using namespace std;

int LinearSearch(int arr[],int key,int size)
{
	int index = 0;

	for (int i = 0; i < size; i++)
	{
		if (arr[i] == key)
		{
			break;
		}
		else
		{
			index = index + 1;
		}

	}

	return index;

}

int main()
{

	int arr[] = { 15,7,5,1,10,3,9,12,13 };
	int key = 1;
	int size = sizeof(arr) / sizeof(arr[0]);

	int index = LinearSearch(arr, key, size);

	std::cout << index << std::endl;


	return 0;
}

We’re trying to search through an array to find the value stored in the ‘key’ variable (1). The array consists of 9 elements (that is from index 0 to index 8). As soon as we find the value stored in the ‘key’ variable, we’ll retrun its index (position in the array).

For that reason we’ve created a function that takes the necessary data as the arguments, that is the array itself, value we’re interested in and the size of the array. One thing to point out here is that the array is always passed into the function as a reference (meaning that only the address of the first element in the array is passed into the array). This is a built in feature of C++ and it’s there so that huge arrays don’t get just simply copied into a function because it’d take up too much memory. This is why we don’t just do it in the function itself.

The algorithm itself consists of a simple for loop that’ll iterate as many times as there are elements in the array. We’re starting at int i=0 because we want to start at index 0, and we go up by 1 until we reach the end of the array (i < size).

If we do encounter the element we’re looking for, we’ll break the loop and return its index, otherwise we’ll keep iterating and everytime we do so we’ll increase the index value by 1.

And that’s all there is to it.

Cheers!

HYPER!locrian