Basic Array Searching in C++ - Coding a Binary Search
(Page 4 of 4 )
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.
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
/ 32 
