Coding a Binary Search - Practices

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.