Practices
  Home arrow Practices arrow Page 4 - Basic Array Searching in C++
Dev Shed Forums 
Administration  
AJAX  
Apache  
BrainDump  
DHTML  
Flash  
Java  
JavaScript  
Multimedia  
MySQL  
Oracle  
Perl  
PHP  
Practices  
Python  
Reviews  
Security  
Style-Sheets  
Web Services  
XML  
Zend  
Zope  
Forums Sitemap 
IBM® developerWorks 
Sun Developer Network 
E-Commerce Hosting 
Linux Web Hosting 
Managed Hosting 
Small Business Hosting 
Mobile Linux 
App Generation ROI 
VPS Hosting 
Weekly Newsletter

 
Developer Updates  
Free Website Content 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us Get Paid 
Request Media Kit
Contact Us 
Site Map 
Privacy Policy 
Support 
 USERNAME
 
 PASSWORD
 
 
  >>> SIGN UP!  
  Lost Password? 
PRACTICES

Basic Array Searching in C++
By: Bryan Roth
  • Search For More Articles!
  • Disclaimer
  • Author Terms
  • Rating: 4 stars4 stars4 stars4 stars4 stars / 32
    2004-12-27

    Table of Contents:
  • Basic Array Searching in C++
  • Sequential Search
  • Binary Search
  • Coding a Binary Search

  • Rate this Article: Poor Best 
      ADD THIS ARTICLE TO:
      Del.ici.ous Digg
      Blink Simpy
      Google Spurl
      Y! MyWeb Furl
    Email Me Similar Content When Posted
    Add Developer Shed Article Feed To Your Site
    Email Article To Friend
    Print Version Of Article
    PDF Version Of Article
     
     
    ADVERTISEMENT


    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.

       · A good refresher on basic array searching, but there are some flaws. Can you fix...
       · Hey Anonymous Loozah,1. I realized that the table examples where the same over...
       · Thanks. I'm looking forward to your next article.
       · on the one hand this is a useful article, on the other, anyone who doesn't know how...
       · Thanks for the quick editing.
     

       

    PRACTICES ARTICLES

    - 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
    - Basic Ideas

     
    Application Delivery: Everything You Wanted to Know, but Didn`t Know You Needed to Ask
    A comprehensive guide to examining the topics of Wide-area Data Services and app....

     
    Best Practices: Safe and Secure Hardware Asset Recovery
    Companies increasingly must meet EPA and local requirements for the disposal of ....

     
    Managing SSL Security in Multi-Server Environments
    Read this white paper to learn how to simplify management of your organization's....

     
    Open Source Security Myths
    Open Source Software (OSS) is computer software whose source code is available t....

     
    Power and Cooling Capacity Management for Data Centers
    This paper describes the principles for achieving power and cooling capacity man....

     




    © 2003-2008 by Developer Shed. All rights reserved. DS Cluster 4 hosted by Hostway
    Stay green...Green IT