Basic Array Searching in C++

Searching arrays for a particular value is a common activity that any programmer should know how to do. Bryan Roth discusses two basic searching methods, sequential and binary, and shows how to code them in C++.

Searching is a very useful operation within the C++ language and any other programming language. Searching is especially useful with arrays. Searching is used daily on the Internet, with surfers using search engines like Google.

Performance is a must with search engines. There are also many ways you can take advantage of searching, like trying to locate a certain transaction number within a large database, finding a certain item located in an inventory database, implementing searching methods within a library catalog, and the list can go on and on. 

Within this article two basic searching methods will be introduced and discussed. These two methods are the sequential search and the binary search. Each searching method has its pros and cons, which will be listed after each explanation.

It is essential to know these two types of searching and how they perform before moving on to more advanced searching methods. With each searching method walkthrough there will be an example followed by an implementation of the example to give you a better understanding of how each searching method works.

{mospagebreak title=Sequential Search}

The sequential search is best used if the array you are searching is unsorted. This method of searching is usually used on small arrays of less than 16 elements. We start the sequential search by first declaring a target to be found. The search initiates at the beginning of the array until it finds the target. 

In the following example we will find a target value of 23 within a one dimensional array. At index 0, 32 is not equal to 23 so we proceed on to the next element.

a[0]

a[1]

a[2]

a[3]

a[4]

32

431

-34

23

12

At index 1, 431 is not equal to 23 so we proceed.

a[0]

a[1]

a[2]

a[3]

a[4]

32

431

-34

23

12

At index 2, -34 is not equal to 23 so we proceed.

a[0]

a[1]

a[2]

a[3]

a[4]

32

431

-34

23

12

Finally at index 3, 23 is equal to 23 and we have found our target.

a[0]

a[1]

a[2]

a[3]

a[4]

32

431

-34

23

12

Now we will implement this example of a sequential search into C++ code. The program below asks the user for a target to be found, then uses a for loop to analyze each element of the array. If the array element is equal to the target it will display that the target was found. Whenever a target is found the variable “flag” will be incremented by 1. At the end of the program if the variable “flag” is less than one, then the target was obviously not found.

#include <iostream>
using namespace std;

int main()
{
  const int arraySize = 5;
  double target;
  int array[arraySize] = {32, 431, -34, 23, 12};
  int flag;

  // flag is used to log how many times the target is encountered.

  flag = 0;

  cout << “Enter a target to be found: “;
  cin >> target;

  for(int cntr = 0; cntr < arraySize; cntr++)
  {
    if(array[cntr] == target)
    {
cout << “Target found in array index ” << cntr << “.”
     << endl;

      flag += 1;
    }
  }
 
  // Test to see if target was found.

  if(flag < 1)
  {
    cout << “Target not found.” << endl;
  }

  return 0;
}

The sequential search does have a pitfall. It is very slow and its performance rating is low. If a person had an array of one million elements, that would mean there could be up to one million comparisons, and that takes time! The sequential search method would be advisable to use only if the array you were searching was unsorted and small.

{mospagebreak title=Binary Search}
  
The binary search is a more efficient way of searching an array of data. As an array starts to get large (greater than 16 elements) the binary search is the suggested method of searching. However, the use of a binary search requires that the array be sorted.

The binary search begins by analyzing the middle term of the array. This determines if the target is in the first half or second half of the array. If the target is in the first half of the array there is no need to check the second half of the array. If the target is in the second half of the array there is no need to check the first half of the array. By knowing in which half the target is located, we eliminate the other half from consideration. This eliminates unnecessary searching, which improves performance. So, if we had a target value of 200,000 in an array of one million elements we could get rid of elements from 500,000 to 1,000,000 without searching! This continues until we find the given target or until it is not found.

In the following example we find a target of 4 in a sorted array. We first find what the first, middle, and last indexes are of the array. The middle index is found by:

middle index = (first index + last index)/2

Here we see that 0 is the first index, 2 is the middle index, and 4 is the last index.

a[0]

a[1]

a[2]

a[3]

a[4]

1

2

3

4

5

Now, we compare the target to the value of the middle index. The value of the middle index is 3, which is greater than the index of 2, meaning that the second half of the array doesn’t need to be considered. We are left with the first half of the array and now repeat the process to find the first, middle, and last indexes. We see that 0 is the first index and 1 is the last index. The middle index is 0 because even though (0 + 1)/2 = 0.5, the value is of data type integer and C++ truncates this making it 0 and does not round the value.

a[0]

a[1]

a[2]

a[3]

a[4]

1

2

3

4

5

Lastly, we compare the target value to the value of the middle index. The value of the middle index is less than the target value so we end up having the first index of the array equaling the target value. This terminates the searching process and we become successful in finding the target value.

a[0]

a[1]

a[2]

a[3]

a[4]

1

2

3

4

5

{mospagebreak title=Coding a Binary Search}

Now, we’ll implement this example of a binary search into C++ code. Since we already know how many elements the array has we assign the array “array” the values of 1, 2, 3, 4, and 5. The while loop continually checks to see if the first index value is less than or equal to the last index value and as long as these conditions are true divides the array until the target is found, just like in the explanation.

#include <iostream>
using namespace std;

int main()
{
  const int arraySize = 5;
  int target;

  // Array size and values already known.

  int array[arraySize] = {1, 2, 3, 4, 5};
  int first, mid, last;

  cout << “Enter a target to be found: “;
  cin >> target;
 
  // Initialize first and last variables.
  first = 0;
  last = 2;

  while(first <= last)
  {
    mid = (first + last)/2;
   
    if(target > array[mid])
    {
      first = mid + 1;
    }
    else if(target < array[mid])
    {
      last = mid + 1;
    }
    else
    {
      first = last + 1;
    }
  }
  // When dividing can no longer proceed you are left with the
  // middle term. If the target equal that term you’re are
  // successful.

  if(target == array[mid])
  {
    cout << “Target found.” << endl;
  }
  else
  {
    cout << “Target not found.” << endl;
  }

  return 0;
}

The binary search does provide better performance than the sequential search. However, the binary search does require the array to be sorted, meaning that you would have to implement a sorting program to sort the data before beginning the binary search. It is suggested that you use the binary search only for large, sorted arrays.

Conclusion

Throughout this article we discussed the basic searching methods for arrays. The sequential search is a unique search that lets you find a target value without sorting the data. However, the sequential search does create a drawback in performance due to constantly making comparisons.

The binary search is a powerful searching method that lets you search through a large array to find a target value with the best performance but requires the array to be sorted. In order for the array to be sorted this might mean creating a sorting script to bog down performance.

So, the searching methods due balance out somewhat in performance ratings, but the binary search prevails allowing you to search large arrays. Both searching methods provide unique strong points but also carry their disadvantages. Both examples of searching were done using one dimensional arrays, but you can utilize searching in multidimensional arrays which could be discussed in a future article. In my next article I will discuss more advanced topics in searching methods.

[gp-comments width="770" linklove="off" ]

chat sex hikayeleri Ensest hikaye