Highlights of this lab:

In this lab, we will discuss binary search in C++.  Suppose you have an array of elements (integer, char, string, etc) and you need to know whether one particular element is in the array, and its index in the array, you need to use some kind of searching algorithm to perform this task.  Binary search is one of these algorithms.  Binary search requires that the array to be searched is sorted, preferably in ascending order. The main idea of binary search is to divide the array into two equal parts and narrow down the range of the array to be searched either to the low part of the array or high part of the array.  Keep doing this until the value is located, or until we realize that the value searched for is not in the array.

An intuitive approach of searching an element in an array is to do a "sequential search", which means we traverse the array from index 0 to ArraySize - 1, where ArraySize is the number of elements in the array.  While sequential search does not require that the array to be searched is sorted, it is much less efficient when the array is sorted.  We will  start up by examining a program using sequential search and then move on to binary search.  A detailed list of topics for this lab is listed below:

Lab Exercise:

• Compile and run the sample program provided.

Click the little computer above for a detailed description.

1. Sequential search

Sequential search is the intuitive approach of searching an array for a particular element.  The idea is to start from either the beginning or end of the array and traverse the array element one by one until the target is located or until all the elements in the array have been visited.  Keep in mind that this approach, although easy to understand, could be very expensive.  This is especially true when the array is very large and the element to be searched for is the farthest one from your starting point.

The following is a sample program demonstrating the idea of sequential search.  The program includes three  files: SeqSearch.h, SeqSearch.cpp, and SeqMain.cpp.

Program listing: SeqSearch.h

```// File name: ~ftp/pub/class/170/ftp/cpp/BinarySearch/SeqSearch.h
// Purpose:   Interface for SeqSearch.cpp

#include <iostream>
#include <iomanip>  // needed by setw

using namespace std;

const int MAXINDEX = 100;

// define a type with the name IntArrayType
// when we need to declare an int array with MAXINDEX elements,
// we could simple write: IntArrayType IntArray;
// IntArray is big enough to hold MAXINDEX integers.
typedef int IntArrayType[MAXINDEX];

////////////////////////
// Function prototypes:
////////////////////////

int SeqSearch(IntArrayType IntArray, int Count, int Target);

void GenerateArray(IntArrayType IntArray, int Count);

void PrintArray(IntArrayType IntArray, int Count);
```

Program listing: SeqSearch.cpp

```//File name: ~ftp/pub/class/170/ftp/cpp/BinarySearch/SeqSearch.cpp
// Purpose:  Implementation of SeqSearch.h

#include "SeqSearch.h"

using namespace std;

////////////////////////////////////////////////////////////////////
// Function: SeqSearch(IntArrayType IntArray, int Count, int Target)
// Purpose:  Given an integer array with "Count" number of elements,
//           try to find "Target".
// Parameters: IntArray: an integer array to hold MAXINDEX elements
//             Count:    number of elements
//             Target:   the integer you are searching for
// Return:     The position of the Target in the array
//             -1 if not found
////////////////////////////////////////////////////////////////////
int SeqSearch(IntArrayType IntArray, int Count, int Target)
{
int k;

for (k = 0; k < Count; k++)
if (IntArray[k] == Target)
return k;

return -1;   // If reach here, Target was not found.
}

//////////////////////////////////////////////////////////////////////
// Function: void GenerateArray(IntArrayType IntArray, int Count);
// Purpose:  Given "Count", generate "Count" number of random integers
//           and put them in IntArray
// Parameters: IntArray: an integer array to hold MAXINDEX elements
//             Count:    number of elements in the array
// Return:     None
//////////////////////////////////////////////////////////////////////
void GenerateArray(IntArrayType IntArray, int Count)
{
int k;

srand((unsigned) time(NULL));  // seed the random number generator

for (k = 0; k < Count; k++)
IntArray[k] = (1000.0 * rand()) / RAND_MAX;
// Note that rand() returns a random integer between 0 and RAND_MAX.
}

////////////////////////////////////////////////////////////////////////////
// Function: void PrintArray(IntArrayType IntArray, int Count);
// Purpose:  Print out the content of "IntArray"
// Parameters: IntArray: an integer array to hold MAXINDEX elements
//             Count:    number of elements in the array
// Return:     None
////////////////////////////////////////////////////////////////////////////

void PrintArray(IntArrayType IntArray, int Count)
{
int k;

//Print header
cout << "Ones ->";
for (k = 0; k < 10; k++)
{
cout << setw(4) << k << " |";
}
cout << endl;
cout << "Tens ||" << setw(60) << setfill('=')<< '|' << endl << setfill(' ');

for (k = 0; k < Count; k++)
{
//Label new rows
if (k % 10 == 0)
cout <<setw(4) << k/10 << " ||";

//Print the array value
cout << setw(4) << IntArray[k] << " |";

//End rows
if (k % 10 == 9)
cout << endl;
}

cout << endl;
}
```

Program listing: SeqMain.cpp

```// File name: ~ftp/pub/class/170/ftp/cpp/BinarySearch/SeqMain.cpp
// Purpose:   Driver program for sequential search
#include "SeqSearch.h"

using namespace std;

int main(void)
{
IntArrayType IntArray;
int Num, Position;

GenerateArray(IntArray, MAXINDEX); // generate 100 random integers

cout << "Here is the content of the array: " << endl;
PrintArray(IntArray, MAXINDEX);

cout << "Enter the number to search for: ";
cin >> Num;

// Search the IntArray for Num and return its position
Position = SeqSearch(IntArray, MAXINDEX, Num);

if (Position == -1)  // not found
cout << "Cannot find " << Num << "." << endl;
else
cout << "Found " << Num << " in position " << Position << ".\n";

return 0;
}```

Here is the running result of the above program:

```hercules[602]% CC -o SeqSearch SeqSearch.cpp SeqMain.cpp
SeqSearch.cpp:
SeqMain.cpp:
hercules[603]% SeqSearch
Here is the content of the array:
Ones ->   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |   9 |
Tens ||===========================================================|
0 ||   7 | 891 | 736 | 275 | 876 |  12 | 413 | 743 | 306 | 843 |
1 || 702 | 581 | 658 | 298 | 810 | 265 |  19 | 834 | 886 | 534 |
2 || 322 |  23 | 717 | 943 | 734 | 859 | 112 | 137 |  29 | 151 |
3 || 439 | 944 | 156 | 842 | 286 | 883 | 730 | 600 | 710 | 178 |
4 || 665 | 525 |  50 | 863 | 657 | 312 | 772 |  95 | 753 | 724 |
5 || 305 | 242 | 701 | 702 | 350 | 855 | 331 | 972 | 619 | 118 |
6 || 651 | 483 | 484 | 865 | 911 | 526 | 497 | 753 | 320 | 869 |
7 || 249 | 702 | 667 | 759 | 542 | 174 | 539 | 140 | 342 | 404 |
8 || 368 | 914 | 476 | 159 |  28 | 601 | 549 | 138 | 186 | 247 |
9 ||  44 | 589 | 144 | 902 |  81 | 245 | 378 | 538 | 792 | 179 |

Enter the number to search for: 95
Found 95 in position 47.
hercules[604]%

```

2. Binary Search

As was mentioned earlier, the idea of binary search is to cut an array (sorted) into two parts and discard the part which could not contain our searching target.  How do we know which part potentially contains our target?  Well, since the array is sorted (generally in ascending order), if one of the two parts of the array, whose largest value is smaller than our target, or  whose smallest value is larger than our target, then this part does not contain our target.

Here is the code for Binary Search:

```// Code for BinarySearch
int BinarySearch(IntArrayType IntArray, int Low, int High, int Target)
{
int Mid, Difference;

while (Low <= High)
{
Mid = (Low + High) / 2;
Difference = IntArray[Mid] - Target;

if (Difference == 0)         // IntArray[Mid] == Target
return Mid;
else if (Difference < 0)     // IntArray[Mid] < Target
Low = Mid + 1;
else
High = Mid - 1;
}

return -1;   // If reach here, Target was not found.
}
```

This is best illustrated with figures.

Suppose we have an integer array with 10 elements, from 0 to 9, and we would like to search for the value 7:

In the beginning, Low = 0 (starting index of the array), High = 9 (ending index of the array) and Mid = (Low+High)/2 = 4. We first check if the value at index 4 is equal to our "Target". IntArray[Mid] = 4 != 7, so we check if the difference between IntArray[Mid] and Target is greater or less than 0. It turns out that it is less than 0, so we update the value for Low: Low = Mid + 1.  See the following figure:

In the above figure,  Low = Mid + 1 = 4 + 1 = 5, High remains unchanged, and Mid = (Low + High)/2 = (5 + 9)/ 2 = 7. The result of this is to ignore the first half of the array (The shaded part) and search for the target 7 in the second half of the array. The reason is that the largest element in the first part of the array, IntArray[4] = 4 is less than Target.

Again, we check if the value at index Mid matches the Target. It does, so we return the index Mid = 7, which is the location for the target.

Following is the complete program demonstrating binary search of an integer array. It contains three 3 files:  BinSearch.h, Binsearch.cpp and BinMain.cpp.

Program listing: BinSearch.h

```// File name: ~ftp/pub/class/170/ftp/cpp/BinarySearch/BinSearch.h
// Purpose:   interface for BinSearch.cpp

#include <iostream>
#include <iomanip>   // needed for setw

using namespace std;

const int MAXINDEX = 100;

typedef int IntArrayType[MAXINDEX];

// Function prototypes:

int BinarySearch(IntArrayType IntArray, int Low, int High, int Target);

void GenerateArray(IntArrayType IntArray, int Count);

void PrintArray(IntArrayType IntArray, int Count);
```

Program listing: BinSearch.cpp

```// File name: ~ftp/pub/class/170/ftp/cpp/BinarySearch/BinSearch.cpp
// Purpose    implementatin of BinSearch.h

#include "BinSearch.h"
using namespace std;

////////////////////////////////////////////////////////////////////////////
// Function: void GenerateArray(IntArrayType IntArray, int Count)
// Purpose:    Generate an array of random integers in ascending order
// Parameters: IntArray: Array of integers in acending order
//             Count :   The number of integers in the array
// Return:     None
////////////////////////////////////////////////////////////////////////////
void GenerateArray(IntArrayType IntArray, int Count)
{
int k;

srand((unsigned) time(NULL)); // seed the rand() function

IntArray[0] = rand()%10; // pick a random number as the first value
for (k = 1; k < Count; k++)
// make sure the array is in ascending order
IntArray[k] = IntArray[k - 1] + rand()%10 + 2;
}

////////////////////////////////////////////////////////////////////////////
// Function: void PrintArray(IntArrayType IntArray, int Count)
// Purpose:    printing the array
// Parameters: IntArray: Array of integers in acending order
//             Count :   The number of integers in the array
// Return:     None
////////////////////////////////////////////////////////////////////////////

void PrintArray(IntArrayType IntArray, int Count)
{
int k;

//Print header
cout << "Ones ->";
for (k = 0; k < 10; k++)
{
cout << setw(4) << k << " |";
}
cout << endl;
cout << "Tens ||" << setw(60) << setfill('=')<< '|' << endl << setfill(' ');

for (k = 0; k < Count; k++)
{
//Label new rows
if (k % 10 == 0)
cout <<setw(4) << k/10 << " ||";

//Print the array value
cout << setw(4) << IntArray[k] << " |";

//End rows
if (k % 10 == 9)
cout << endl;
}

cout << endl;
}

////////////////////////////////////////////////////////////////////////////
// Function:
//     int BinarySearch(IntArrayType IntArray, int Low, int High, int Target)
// Purpose:    search "Target" in an ordered integer array
// Parameters: IntArray: Array of integers in acending order
//             Low:      The starting index
//             High:     The ending index
//             Target:   The integer value to search
// Return:     The index of the value if found
//             -1 if not found
////////////////////////////////////////////////////////////////////////////
int BinarySearch(IntArrayType IntArray, int Low, int High, int Target)
{
int Mid, Difference;

while (Low <= High)
{
Mid = (Low + High) / 2;
Difference = IntArray[Mid] - Target;

if (Difference == 0)         // IntArray[Mid] == Target
return Mid;
else if (Difference < 0)     // IntArray[Mid] < Target
Low = Mid + 1;
else
High = Mid - 1;
}

return -1;   // If reach here, Target was not found.
}
```

A few comments about the function to generate an array for binary search.  Since binary search requires that the array be sorted in ascending order, when using the random number generator to generate integers, we need to make sure that  the integers are sorted.  The way to do it is to pick a random number as the first element of the array.  The second value is the first one plus a random integer between 0 and 9, plus 2.  This way, we have an array of random integers sorted in ascending order without repeating values.

Program listing: BinMain.cpp

```// File name:  ~ftp/pub/class/170/ftp/cpp/BinarySearch/BinMain.cpp
// Purpose:    Driver program for binary search program

#include "BinSearch.h"
using namespace std;

int main(void)
{
IntArrayType IntArray;
int Num, Pos;

GenerateArray(IntArray, MAXINDEX); // generate sorted integer array

cout << "The contents of the array are: " << endl;
PrintArray(IntArray, MAXINDEX);

cout << "Enter the integer to search for: " << endl;
cin >> Num;

Pos = BinarySearch(IntArray, 0, MAXINDEX - 1, Num);

if(Pos == -1)
cout << "Not found" << endl;

else
cout << "Number " << Num << " found in Position " << Pos << endl;

return 0;
}
```

Running result:

```hercules[560]% CC -o BinSearch BinSearch.o BinMain.o
hercules[561]% ./BinSearch
The contents of the array are:
Ones ->   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |   9 |
Tens ||===========================================================|
0 ||   0 |   2 |  11 |  17 |  28 |  38 |  42 |  47 |  51 |  53 |
1 ||  57 |  65 |  67 |  70 |  81 |  90 |  97 | 106 | 114 | 122 |
2 || 131 | 134 | 138 | 140 | 145 | 154 | 163 | 166 | 176 | 183 |
3 || 191 | 195 | 202 | 209 | 214 | 220 | 222 | 232 | 240 | 249 |
4 || 252 | 262 | 269 | 277 | 280 | 286 | 292 | 300 | 302 | 312 |
5 || 318 | 325 | 329 | 331 | 341 | 343 | 351 | 353 | 356 | 358 |
6 || 363 | 367 | 377 | 381 | 392 | 402 | 410 | 416 | 420 | 429 |
7 || 439 | 442 | 445 | 447 | 455 | 458 | 464 | 473 | 479 | 490 |
8 || 492 | 494 | 498 | 507 | 517 | 521 | 528 | 536 | 546 | 550 |
9 || 561 | 565 | 570 | 581 | 592 | 599 | 605 | 611 | 614 | 623 |

Enter the integer to search for:
447
Number 447 found in Position 73
hercules[562]%
```

3. Lab Exercise

• Transfer the BinMain.cpp BinSearch.cpp BinSearch.h files from the CS Dept's anonymous ftp site to your Hercules account space. Do that by:
1. Entering the commands:
``` cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/BinMain.cpp BinMain.cpp
cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/BinSearch.cpp BinSearch.cpp
cp /net/data/ftp/pub/class/170/ftp/cpp/BinarySearch/BinSearch.h BinSearch.h

```
2. OR, by doing a copy and paste from the screen to an edit session,
3. OR, by using the command line FTP program using this information:
The path: pub/class/170/ftp/cpp/BinarySearch
The files: BinMain.cpp, BinSearch.h, BinSearch.cpp

• Compile and run this program. Those compile/link commands (on Hercules) are:
CC -c BinSearch.cpp
CC -c BinMain.cpp
CC -o BinSearch BinSearch.o BinMain.o

• To get a better understanding of how the Binary Search is working, add some statements to the routine. i.e. Make these changes in BinSearch.cpp
• Create a local variable called "LoopCtr" and initialize it to 1.
• After the
Difference = IntArray[Mid] - Target; statement, add some cout statements to print the values of
```Target:   Mid:  Difference:  LoopCtr:
```
• After your new cout statements, add these statements:
PrintArray(IntArray, Mid);
LoopCtr++;

Compile the BinSearch.cpp program again and then link and run it. Remember, you only have to compile the BinSearch.cpp program again. Don't bother recompile the BinMain.cpp program. You haven't made any changes to that one.

Perform a few runs, trying the search with values at the beginning of the array, the middle of the array, and values towards the end of the array.

When you have run the program a few times, answer these questions:

```
What happens to the size of the array being searched in each iteration of the search loop?

i.e. Is it _______ doubled in size or  _______ halved in size?

How many times does the function loop to find the first number in the array? _______

How many times does the function loop to find the middle number in the array? _______

How many times does the function loop to find the last number in the array? ______

```

• Now go back and have a look at the code for the Sequential Search.
```int SeqSearch(IntArrayType IntArray, int Count, int Target)
{
int k;

for (k = 0; k < Count; k++)
if (IntArray[k] == Target)
return k;

return -1;   // If reach here, Target was not found.
}
```
Without running the sequential search program, just look at that code and the following printout of an array. What would be the value of the loop counter "k" if you were to perform sequential searches for the following values?
```
Search Value	k Value (i.e. the loop counter)

27         _______?

51         _______?

176        _______?

355        _______?

608        _______?

Suppose your array contained 1,000,000 elements.
How many times would you have to loop to find the largest value in the array?
How many times would the Binary Search program have to loop to find  that value?
```
```
The contents of the array are:
Ones ->   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |   9 |
Tens ||===========================================================|
0 ||   5 |   8 |  18 |  27 |  30 |  41 |  46 |  51 |  58 |  68 |
1 ||  73 |  75 |  80 |  89 |  98 | 105 | 109 | 118 | 127 | 134 |
2 || 144 | 148 | 155 | 165 | 167 | 176 | 185 | 189 | 199 | 210 |
3 || 212 | 214 | 221 | 227 | 233 | 237 | 240 | 244 | 255 | 263 |
4 || 270 | 276 | 281 | 290 | 295 | 301 | 309 | 316 | 321 | 325 |
5 || 329 | 333 | 335 | 344 | 355 | 357 | 359 | 362 | 364 | 373 |
6 || 381 | 390 | 396 | 403 | 406 | 413 | 419 | 427 | 429 | 440 |
7 || 448 | 459 | 462 | 467 | 473 | 477 | 486 | 493 | 498 | 501 |
8 || 504 | 512 | 516 | 521 | 526 | 531 | 541 | 550 | 556 | 558 |
9 || 560 | 565 | 574 | 578 | 587 | 595 | 597 | 600 | 604 | 608 |

```

 CS Dept Home Page CS Dept Class Files CS115 Lab Files
This page last modified: Tuesday, 17-Apr-2012 08:59:35 CST
Copyright: Department of Computer Science, University of Regina.