Basics of Using Arrays in C++

Because an array is used to store a collection of data, it is important to know how to use them efficiently.

Searching Arrays

We often need to search an array to see if a value is inside of it or not. While some languages do this for you, C++, because of it’s age, doesn’t.

Linear Search

Linear Search means that you are going to search one item at a time until you find it. This is best if your array isn’t already sorted.

You will need to start at the front of the array, and work your way to the end.

Assuming we know the length of the array, we could use some code like the following:

const int ARRAY_SIZE = 10;
int[] myArray[ARRAY_SIZE];
bool found = false;
int searchFor = 36;
// assume data gets filled here some how

for(int i = 0; i < ARRAY_SIZE; i++) 
{
  if(myArray[i] == searchFor)
  {
    found = true;
    break;
  }
}

This works find for small amounts of data, or data that isn’t sorted. This can also be put into a function, to make it easier to work with.

bool findItem(int items[], int length, int searchFor);

int main()
{
  const int ARRAY_SIZE = 10;
  int[] myArray[ARRAY_SIZE];
  int searchFor = 36;
  // assume data gets filled here some how
  bool found = findItem(myArray, ARRAY_SIZE, searchFor);

  return 0;
}
bool findItem(int items[], int length, int searchFor)
{
  bool returnValue = false;
  for(int i = 0; i < ARRAY_SIZE; i++) 
  {
    if(myArray[i] == searchFor)
    {
      returnValue = true;
      break;
    }
  }
  return returnValue;
}

If we have a large number of elements, then it is better to search for something using a binary search;

Binary Search

The binary search works on the premise of divide and conquer. If pick a value in the center, I can eliminate half of my options by knowing if the item is smaller or larger than my center value.

Of course, this only works if your array is sorted.

bool binarySearch(int items[], int high, int searchFor)
{
    int low = 0;
    int mid;
    bool returnValue = false;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (searchFor < items[mid])
        {
            high = mid - 1;
        }
        else if (searchFor == items[mid])
        {
            returnValue = true;
            high = -1;
        }
        else
        {
            low = mid + 1;
        }
    }

    return returnValue;
}

Sorting Data

Of course, the binary search requires that data be sorted. But what if your data isn’t sorted? Well, there are various forms of sorting algorithms, from the inefficient bubble sort (but easy to understand), to the efficient quick sort (but harder to understand and thus build).

The book references the selection sort, which finds the smallest number in an array, and puts it into the first position, then finds the second smallest, and puts it into the second position, etc. It does this through a series of loops and if statements.

void selectionSort(double list[], int listSize)
{
    double currentMin;
    int currentMinIndex;
    for (int i = 0; i < listSize; i++)
    {
        currentMin = list[i];
        currentMinIndex = i;

        for (int j = i; j < listSize; j++)
        {
            if (currentMin > list[j])
            {
                currentMin = list[j];
                currentMinIndex = j;
            }
        }

        if (currentMinIndex != i)
        {
            list[currentMinIndex] = list[i];
            list[i] = currentMin;
        }
    }
}

Basics of Using Arrays in C++ was originally found on Access 2 Learn