Home arrow Practices arrow Page 4 - Basic Array Searching in C++

Coding a Binary Search - Practices

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++.

TABLE OF CONTENTS:
  1. Basic Array Searching in C++
  2. Sequential Search
  3. Binary Search
  4. Coding a Binary Search
By: Bryan Roth
Rating: starstarstarstarstar / 47
December 27, 2004

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

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.



 
 
>>> More Practices Articles          >>> More By Bryan Roth
 

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PRACTICES ARTICLES

- Calculating Development Project Costs
- More Techniques for Finding Things
- Finding Things
- Finishing the System`s Outlines
- The System in So Many Words
- Basic Data Types and Calculations
- What`s the Address? Pointers
- Design with ArgoUML
- Pragmatic Guidelines: Diagrams That Work
- Five-Step UML: OOAD for Short Attention Span...
- Five-Step UML: OOAD for Short Attention Span...
- Introducing UML: Object-Oriented Analysis an...
- Class and Object Diagrams
- Class Relationships
- Classes

Developer Shed Affiliates

 


Dev Shed Tutorial Topics: