CS115 Lab: Binary Search

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:


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 


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.