Using Linear Search In C++

Jason Moore

Programmers will often search data for specific items. The most basic way is to use a linear search. This algorithm will form the foundation of your searching.

 

Introduction

I apologize for this article being so long in getting here. There was a dust alert in my area of Texas and thusly very poor air quality for a while. My head did not like this and I am just now getting back to normal. So, with that out of the way, let’s talk about our first search algorithm.

The technique I am talking about today will be the linear search process. You might ask yourself why you would need to do this. Well, commonly data is in a database. If we want to use C++ essentials our tool to work with it, then it is nice to have it in a text file. To be useful, this would be a significant amount of data. It could be sales data or temperature readings, for example. Now let me preface this by saying we would only want to work on a large amount of data. We aren’t going to bother with a 30 line spreadsheet. However, if we have 100,000 items to analyze quickly, then C++ is a good tool.

Let’s talk about algorithms a bit first. An algorithm is a step-by-step process that is used by a computer to solve a problem or make a decision. Algorithms in this case let you search data for a specific value or entry, which is very useful. This will also let you check to see if the value you are expecting is really there. This can also be important. These techniques are usually applied to data in arrays.

Linear Search

A linear search is very simple because it takes data items one at a time in the order they are given. It accomplishes this through the use of a loop. The most popular type of loop is a <for loop>. Items are looked at one at a time until it gets to the end of the data. The values are then compared to the previous value to see if it is the value we are looking for.

So lets go over what this linear algorithm will look like. We will have variables to indicate whether the correct value is found or not, the position among the data, and a loop counter. We initially set our value variable to false. The program can change it to true and stop running if the value is found. We set our position to the first item on the list. Our loop variable will be initialized to zero.

Next, we will create a loop that will run through our data items. It should tell us where the item was located in our set of data, if it finds it.

Technically, the linear search is inefficient. If you have a data set with 100,000 items, then it will have to search through every one of them first if the value is in the last spot. This can cause a program to run for a lot longer than it should. If you have something time sensitive to calculate, this would be unacceptable. If your data is very small or not time sensitive, then it would be fine to run this. However, if it is that small, then you probably don’t need an algorithm in the first place.

Example

This is the program I wrote to show a linear search. It is a continuation of the program I have been working on to showcase these techniques. It is not advanced by any means. There are many ways to improve it. I did not put anything in functions either. This is all because I can put those implementations in future articles. So we are going one step at a time and I think if you are following along, it will help you learn more.

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
 vector<int> rogue;
 ifstream inputfile;
 int pierce =0;
 int highest =0;
 int vectorsize =0;
 int search_value =0;
 int i =0;
 inputfile.open ("numberfile.txt");

 while (inputfile >> pierce)
 rogue.push_back(pierce);

inputfile.close();

// printing array values
for (int count = 0; count < rogue.size(); count++)
{
 cout << rogue[count] << endl;
}
cout << endl;

// finding highest value in the array
highest = rogue[0];
for (int count = 1; count < rogue.size(); count++)
{
 if (rogue[count] > highest)
 highest = rogue[count];
}

 cout <<"The largest of these values is " << highest << endl;

//Showing size of array
 vectorsize = rogue.size();
 cout << endl;
 cout << "The size of this array is " << vectorsize << " values. " << endl;

// Performing a linear search

 cout << "Enter the value to search for: ";
 cin >> search_value;

 for (i = 0; i < vectorsize; i++)
 {
 if (search_value == rogue[i])
 {
 cout << "Element is found at " << i + 1 << " place in the list ";
 break;
 }
 }
 if (i == vectorsize)
 cout << "Element is not present in the list ";

return 0;
}

In this program, I am reading a bunch of data from a text file. It all goes into a <vector> container. Once we have the data, we just have some fun with it. I print it all out, find the highest value, and show the size of the array. These can be very useful things to do. I also could have also done some statistical processes to this data as well.

However, since this chapter is talking about linear search, let’s go over that in more detail. The first thing I do is ask the user what they are searching for. Since we have numerical data, we are going to assume they are looking for some value in particular.

So that response gets put into a variable which is defined at top of the program. Next I wrote a <for loop> to look at each item in the array. Then I also added a nested loop to compare the item we are searching for with the current value in every part of the array. Then finally I added a condition and message in case the value was not found in the array.

So in this chapter I talked about how to do a linear search of an array. I use the <vector> container because it is much more flexible than the array container. We can successfully use this to find a value that you know is there and give its reported position in the array. Next time I will be going over the binary search method.

You should also read: