Linear search. Development of a class that implements linear search in a one-dimensional array

This topic discusses the implementation of a linear search for an element in a one-dimensional array. For the purpose of demonstration, the LSearch<T> class has been developed, which contains tools for organizing a linear search.

---

Contents

• 1. Linear search. Concept
• 2. Developing a templated LSearch<T> class that implements linear search
  • 2.1. Task
  • 2.2. General structure of the class. Internal variables
  • 2.3. Class constructors
    • 2.3.1. Constructor without parameters
    • 2.3.2. A constructor that initializes the internal fields of the class with an input array
    • 2.3.3. Copy constructor LSearch(const LSearch&)
  • 2.4. Methods of access to an instance of the array
    • 2.4.1. Method Get(). Get pointer to the internal array
    • 2.4.2. Method Set(). Set new values in the array
  • 2.5. Destructor
  • 2.6. Operator function operator=()
  • 2.7. Methods of implementation of linear search
    • 2.7.1. Method IsItem(). Determining if there is an element (key) in an array
    • 2.7.2. Method NumOccurs(). Get the number of occurrences of an element in an array
    • 2.7.3. Method GetPos(). Get an array of positions of occurrences of an element in an array
  • 2.8. Method Print(). Displaying the contents of an array on the screen
  • 2.9. Function main(). Testing class performance
  • 2.10. Class text (abridged version)
• Related topics

---

Search other websites:

1. Linear search. Concept

Linear search is one of the simplest ways to find data. The purpose of a linear search is to find the required element (key) in the data array. In the linear search algorithm, each element of the array is sequentially compared with the key until the desired element is found or the entire array is scanned.

In the context of linear search, the following tasks can arise:

• determine the presence of a given element in an array (data set);
• determine the number of occurrences of a given element in the array;
• determine the position number or array of position numbers of the given element in the array.

The linear search implementation can be extended for use in multidimensional arrays.

  ⇑

2. Developing a templated LSearch<T> class that implements linear search

A template class that implements linear search can be placed in a separate module (file) and used as needed. The developed class can be used for basic types of the C ++ language such as int, double, char and others.

If it becomes necessary to use this class for an array of instances of another class, then in this (other) class you need to override the comparison operation (==), which compares two instances of the class for equality. But that’s another topic.

  ⇑

2.1. Task

Develop a class that contains facilities for performing linear search on a one-dimensional array. The class needs to implement the following fields and methods:

• internal variables that describe the array;
• all the necessary class constructors;
• access methods to the array in the class;
• destructor;
• operator function operator=(), which overloads the assignment operator;
• methods for implementing linear search both in the class array and in the external array.

Demonstrate the work of the class in the main () function.

  ⇑

2.2. General structure of the class. Internal variables

Since linear search is implemented in a one-dimensional array, the internal data of the class is a one-dimensional array A and its dimension count.

The class is templated and works with the generic type T. After entering the internal variables, the general view of the class for an application of type Console Application is as follows

#include <iostream>
using namespace std;

// A templated class that implements linear search in a one-dimensional array
template <class T>
class LSearch
{
private:
  // Internal variables
  T* A; // array
  int count; // the number of items in array
}

void main(void)
{
}

  ⇑

2.3. Class constructors

The class body in the public section contains the codes of the class constructors.

2.3.1. Constructor without parameters

The parameterless constructor sets internal variables to zero values.

The implementation of such a constructor provides for:

• adding an array of data using the Set() method and processing it;
• using linear search methods for arrays that are not the data of the current class instance (for any other external arrays).

After adding a constructor to the public section, the general view of the class is as follows

// A templated class that implements linear search on a one-dimensional array
template <class T>
class LSearch
{
private:
  // Internal variables
  T* A; // array
  int count; // the number of elements in the array

public:
  // Constructor without parameters
  LSearch()
  {
    A = nullptr;
    count = 0;
  }
}

  ⇑

2.3.2. A constructor that initializes the internal fields of the class with an input array

This constructor is required when the program has an external data array. The constructor makes a copy of the external array to the internal one for further processing.

// A constructor that receives an input array,
// with which the elements of the internal array are initialized
LSearch(T* _A, int _count)
{
  // 1. Checking if _count value is correct
  if (_count <= 0)
  {
    A = nullptr;
    count = 0;
    return;
  }

  // 2. Set the new number of elements
  count = _count;

  // 3. Allocate memory for array A
  try
  {
    A = new T[count];
  }
  catch (bad_alloc e)
  {
    cout << e.what() << endl;
    return;
  }

  // 4. Copy A = _A
  for (int i = 0; i < count; i++)
    A[i] = _A[i];
}

  ⇑

2.3.3. Copy constructor LSearch(const LSearch&)

Since the memory in the class array is allocated dynamically, it is necessary to declare a copy constructor. More details about the need to use the copy constructor and the assignment operator in the class are described here.

// Copy constructor - redirect to constructor with two parameters
LSearch(const LSearch& _A) :LSearch(_A.A, _A.count)
{
}

  ⇑

2.4. Methods of access to an instance of the array

To access the internal array of the class, two methods Get(), Set() are implemented. These methods are located in the public section.

2.4.1. Method Get(). Get pointer to the internal array

Using the Get() method, you can get a pointer to the internal array A of the class. The method gets a reference to an external variable that gets the value of the number of elements in array A.

// Method that returns a pointer to the internal array A of the class
T* Get(int* _count)
{
  *_count = count;
  return A;
}

  ⇑

2.4.2. Method Set(). Set new values in the array

The Set() method allows you to set a new array as being processed.

// Method for modifying an array in the current instance
void Set(T* _A, int _count)
{
  // 1. Checking if _count value is correct
  if (_count <= 0)
  {
    A = nullptr;
    count = 0;
    return;
  }

  // 2. Free the memory allocated for array A of the current instance
  if (count > 0)
    delete[] A;

  // 3. Set the new number of elements
  count = _count;

  // 4. Allocate a new chunk of memory for A
  try
  {
    A = new T[count];
  }
  catch (bad_alloc e)
  {
    cout << e.what() << endl;
    return;
  }

  // 5. Assign A = _A
  for (int i = 0; i < count; i++)
    A[i] = _A[i];
}

  ⇑

2.5. Destructor

The destructor frees the memory used for the internal array A. The destructor is called automatically when a class instance is destroyed.

// Destructor
~LSearch()
{
  if (count > 0)
  {
    delete[] A;
  }
}

  ⇑

2.6. Operator function operator=()

In the class, you need to override the assignment operator =, which assigns instances of the LSearch<T> class. This is necessary to avoid the disadvantages of bitwise copying that occurs when pointers are used in a class. More details about the need to override the assignment operator in the class are described here.

// Overridden assignment operator
LSearch& operator=(LSearch& _A)
{
  // Invoke the method Set()
  Set(_A.A, _A.count);

  // Return the current instance
  return *this;
}

  ⇑

2.7. Methods of implementation of linear search

2.7.1. Method IsItem(). Determining if there is an element (key) in an array

The IsItem() method determines if an item is in the array. The method scans the array sequentially from start to finish. The method returns true or false.

In the class, the method has two overloaded implementations. The first implementation is for any array. The second implementation applies to the internal array of the current instance of the class.

// Overloaded method IsItem()
// Determining if the element key is in the array given by the input parameter
bool IsItem(T* _A, int _count, T key)
{
  for (int i = 0; i < _count; i++)
    if (_A[i] == key) // as soon as the element is found, then exit from the function
      return true;
  return false;
}

bool IsItem(T key)
{
  // call a generic method with the data of the current instance
  return IsItem(this->A, this->count, key);
}

  ⇑

2.7.2. Method NumOccurs(). Get the number of occurrences of an element in an array

The NumOccurs() method allows you to get the number of occurrences of a given key in an array. The method has two overloaded implementations: for the outer array and for the inner array of the class.

// Overloaded method NumOccurs()
// Calculate the number of occurrences of an element in the array given by the input parameter
int NumOccurs(T* _A, int _count, T key)
{
  int num = 0;
  for (int i = 0; i < _count; i++)
    if (_A[i] == key)
      num++;
  return num;
}

// Calculate the number of occurrences of an element in an array
// given in the current instance of the class
int NumOccurs(T key)
{
  // Call the method of the same name with the current data
  return NumOccurs(A, count, key);
}

  ⇑

2.7.3. Method GetPos(). Get an array of positions of occurrences of an element in an array

The GetPos() method returns an array of positions of occurrences of the specified key in the array. Inside the GetPos() method, memory is allocated for the resulting array. Therefore, when using the method, you need to take care of freeing this memory.

// Overloaded method GetPos()
// Return an array of positions of occurrence of a given element in the input array
int* GetPos(T* _A, int _count, T key, int& nPos)
{
  // 1. Checking if count is valid
  if (_count <= 0)
  {
    return nullptr;
  }

  // 2. Declare internal variables
  int* P = nullptr; // The resulting array

  // 3. Calculate the number of occurrences of nPos
  nPos = NumOccurs(_A, _count, key);

  // 4. Allocate memory for resulting array P
  try
  {
    P = new T[nPos];
  }
  catch (bad_alloc e)
  {
    cout << e.what() << endl;
    return nullptr;
  }

  // 5. The loop of position numbers calculation
  int t = 0;
  for (int i = 0; i < _count; i++)
    if (_A[i] == key)
      P[t++] = i;

  // 6. Return a pointer to an array of positions
  return P;
}

// Return an array of positions in the array of the current instance
int* GetPos(T key, int& nPos)
{
  // Call the function of the same name
  return GetPos(A, count, key, nPos);
}

  ⇑

2.8. Method Print(). Displaying the contents of an array on the screen

The Print() method is implemented for a console application and prints the values of the array elements to the screen.

// Method that prints the data of the instance array to the screen with the comment text
void Print(const char* text)
{
  cout << text << endl;
  cout << "count = " << count << endl;
  for (int i = 0; i < count; i++)
    cout << A[i] << " ";
  cout << endl;
}

  ⇑

2.9. Function main(). Testing class performance

Testing of the class operation is carried out in the main() function for a console application (of the Console Application type).

void main(void)
{
  // Demonstrate the LSearch<T> class
  // An instance of an array of type int - a constructor without parameters is called
  LSearch<int> L1;

  // The test array of numbers of type int
  int A[] = { 0, 2, 3, 5, 7, 3, 4, 8, 4, 0, 0, 2 };
  int count = 12; // the number of items in array A

  // Add array A to instance L1
  L1.Set(A, count); // checking the Set() method

  // Determine if there is actually element 3
  if (L1.IsItem(3))
  {
    // If so, output the number of occurrences of element 3 in array A
    int k = L1.NumOccurs(3);
    cout << "k = " << k << endl;
  }
  L1.Print("L1:");

  // Checking the copy constructor
  LSearch<int> L2 = L1;
  L2.Print("L2:");

  // Checking the assignment operator
  LSearch<int> L3;
  L3 = L1;
  L3.Print("L3:");

  // Checking the Get() method - fill a new array with values
  int* A2;
  int count2;
  A2 = L3.Get(&count2);

  // Print the array A2
  cout << "A2.count = " << count2 << endl;
  for (int i = 0; i < count2; i++)
    cout << A2[i] << " ";
  cout << endl;

  // Checking the GetPos() method - get an array of positions of occurrences
  int nPos;
  int* P = L1.GetPos(0, nPos);

  cout << "nPos = " << nPos << endl;
  for (int i = 0; i < nPos; i++)
    cout << P[i] << " ";
  cout << endl;

  // After use, you need to free the memory allocated for the array P
  if (P != nullptr)
    delete[] P;

  // Checking a constructor that receives an input array of double type as a parameter
  double B[] = { 3.1, 2.8, 0.85, -10.5 }; // an array
  LSearch<double> L4(B, 4); // a constructor with two parameters is called
  L4.Print("L4");

  // Determine the number of occurrences of number 0.85 in an array
  int k = L4.NumOccurs(0.85);
  cout << "k = " << k << endl;
}

The result of the program

k = 2
L1:
count = 12
0 2 3 5 7 3 4 8 4 0 0 2
L2:
count = 12
0 2 3 5 7 3 4 8 4 0 0 2
L3:
count = 12
0 2 3 5 7 3 4 8 4 0 0 2
A2.count = 12
0 2 3 5 7 3 4 8 4 0 0 2
nPos = 3
0 9 10
L4
count = 4
3.1 2.8 0.85 -10.5
k = 1

  ⇑

2.10. Class text (abridged version)

By sequentially completing all the previous points, you can get the full text of the LSearch<T> class. Below is the program code of the class in abbreviated form.

#include <iostream>
using namespace std;

// A templated class that implements linear search in a one-dimensional array
template <class T>
class LSearch
{
private:
  // Internal variables
  T* A; // array
  int count; // the number of elements in array

public:
  // Constructors
  // Constructor without parameters
  LSearch()
  {
    ...
  }

  // A constructor that receives an input array
  // that initializes the elements of the internal array
  LSearch(T* _A, int _count)
  {
    ...
  }

  // Copy constructor - redirect to constructor with two parameters
  LSearch(const LSearch& _A) :LSearch(_A.A, _A.count)
  { }

  // ------- Methods of access to an instance of an array -------------
  // Method for modifying an array in the current instance
  void Set(T* _A, int _count)
  {
    ...
  }

  // Method that returns a pointer to the internal array of the class
  T* Get(int* _count)
  {
    ...
  }

  // Destructor
  ~LSearch()
  {
    ...
  }

  // Overridden assignment operator
  LSearch& operator=(LSearch& _A)
  {
    ...
  }

  // ------ Search methods ----------
  // 1. Overloaded method IsItem()
  // Determining if the key element is in the array given by the input parameter
  bool IsItem(T* _A, int _count, T key)
  {
    ...
  }

  // Determining if a key element is in an array that is specified in an instance of a class
  bool IsItem(T key)
  {
    ...
  }

  // 2. Overloaded method NumOccurs()
  // Calculate the number of occurrences of an element in the array given by the input parameter
  int NumOccurs(T* _A, int _count, T key)
  {
    ...
  }

  // Calculate the number of occurrences of an element in an array
  // given in the current instance of the class
  int NumOccurs(T key)
  {
    ...
  }

  // 3. Overloaded method GetPos()
  // Return an array of positions of occurrence of a given element in the input array
  int* GetPos(T* _A, int _count, T key, int& nPos)
  {
    ...
  }

  // Return an array of positions in the array of the current instance
  int* GetPos(T key, int& nPos)
  {
    ...
  }

  // Method that displays the data of the instance array on the screen with the comment text
  void Print(const char* text)
  {
    ...
  }
};

void main(void)
{
  ...
}

  ⇑

---

Related topics

• Developing a class that implements an array of char* strings
• Developing a Random class for generating random numbers

  ⇑

---