Binary Search (Nonrecursive)


Program Listing

BinarySearch.cpp

/************************************************************************
*                                                                       *
*   Program:    BinarySearch.cpp                                        *
*                                                                       *
*   Abstract:   This program will perform a binary search of a list     *
*               for a specified value                                   *
*                                                                       *
************************************************************************/

//  Header files

#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

//  Function prototypes

int BinarySearch(int array[], int size, int value);
void Sort(int array[], int size);

/************************************************************************
*                                                                       *
*   Function:   main                                                    *
*                                                                       *
*   Purpose:    To perform a binary search of a list for a specified    *
*               value                                                   *
*                                                                       *
************************************************************************/

int main() {

    const int sentinel = -1;
    const int maxSize = 100;
    
    int array[maxSize];
    
    int size = maxSize;

//  Create an array of random integers

    for (int i = 0; i < size; i++)
        array[i] = rand() % 1000;

//  Sort and print the array
        
    Sort(array, size);
        
    for (int i = 0; i < size; i++)
        cout << array[i] << ' ';
    cout << endl << endl;

//  Search the array for values given by the user

    cout << "Enter a number to be search for (enter " << sentinel
         << " to quit):  " << flush;
    int value;
    cin >> value;
    while (value != sentinel) {
    
    //  Search the array
    
        int pos = BinarySearch(array, size, value);
    
    //  Report the results
    
        if (pos >= 0)
            cout << value << " was found in position " << pos << endl;
        else
            cout << value << " was not found" << endl;

        cout << "Enter a number to be search for (enter " << sentinel
             << " to quit):  " << flush;
        cin >> value;
    }
    
    cout << endl << "Good-bye" << endl;
    return 0;
}

/************************************************************************
*                                                                       *
*   Function:   BinarySearch                                            *
*                                                                       *
*   Purpose:    To perform a binary search of a list for a specified    *
*               value                                                   *
*                                                                       *
************************************************************************/

int BinarySearch(int array[], int size, int value) {

    bool found = false;
    int left = 0;
    int right = size - 1;
    int middle;

//  Search until value is found or there is nowhere else to look

    while (left <= right) {
        middle = (left + right)/2;
        if (value < array[middle])
            right = middle - 1;
        else if (value > array[middle])
            left = middle + 1;
        else {
            found = true;
            break;
        }
    }

//  Determine why loop terminated and return appropriate value

    if (found)
        return middle;
    else
        return -1;
}

/************************************************************************
*                                                                       *
*   Function:   Sort                                                    *
*                                                                       *
*   Purpose:    To sort a list of integers into ascending order         *
*                                                                       *
************************************************************************/

void Sort(int array[], int size) {

//  Use a quick-and-dirty bubble sort

    for (int i = 0; i < size - 1; i++)
        for (int j = 0; j < size - 1 - i; j++)
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
    return;
}

Sample Run

5 10 22 31 51 54 60 61 67 71 84 85 86 88 89 96 102 113 116 134 137 139 143 145 160 165 181 183 188 201 212 225 233 248 259 262 306 311 318 327 336 343 353 367 394 403 406 414 419 422 444 457 475 479 495 505 514 515 516 521 524 536 543 561 562 566 606 627 628 629 644 653 670 693 729 736 738 749 751 754 757 758 760 767 803 825 834 838 851 882 894 920 945 962 966 967 978 979 983 990 

Enter a number to be search for (enter -1 to quit):  212
212 was found in position 30
Enter a number to be search for (enter -1 to quit):  5
5 was found in position 0
Enter a number to be search for (enter -1 to quit):  990
990 was found in position 99
Enter a number to be search for (enter -1 to quit):  3
3 was not found
Enter a number to be search for (enter -1 to quit):  999
999 was not found
Enter a number to be search for (enter -1 to quit):  500
500 was not found
Enter a number to be search for (enter -1 to quit):  -1

Good-bye



Return to Lectures page


e-mail me at robbk@hsc.edu

This page was last modified on Tue Dec 7 16:05:02 1999 .

URL: http://people.hsc.edu/faculty-staff/robbk/Coms261/Examples/BinarySearch.html

Return to Coms 261 home page