1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
|
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
int binarySearch(string, int, string);
int main()
{
const int NUM_NAMES = 10;
string names[NUM_NAMES] = { "baboon", "giraffe", "hippopotamus", "lion", "monkey", "rhinoceros", "tapir", "tiger", "wildebeest", "zebra" };
string word;
int result;
cout << "Please enter one of hte following words: " << endl;
cout << "baboon, giraffe, hippopotamus, lion, monkey, " << endl;
cout << "rhinoceros, tapir, tiger, wildebeest, zebra." << endl;
getline(cin, word);
result = binarySearch(names, NUM_NAMES, word);
if (result == -1)
cout << "That word does not exist in the array." << endl;
else
{
cout << "That word is found at element " << result << " in the array." << endl;
}
cin.ignore();
return 0;
}
int binarySearch(string names[], int size, string value)
{
int first = 0,
last = size - 1,
middle,
position = -1;
bool found = false;
while (!found && first <= last)
{
middle = (first + last) / 2;
if (names[middle] == value)
{
found = true;
position = middle;
}
else if (names[middle] > value)
last = middle - 1;
else
first = middle + 1;
}
return position;
}
|