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

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

  
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



 
 
>>> 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: