C++

Forum

 
binary search method

cmt9000 (13)
I need to write a binary search program that uses templates and that can take 2 types of data.

I think I have it down pretty good, but I am getting 4 persistent errors that I cannot figure out.

The errors are:

2x cannot convert argument1 from 'int' to 'const char *'
2x cannot convert argument1 from 'std::string' to 'const char *'


I know the strcmp function is expecting 2 arguments of type char, but I can't figure out a method to compare the two strings. In Java, I know I could use the compareTo method. Is there a similiar method in c++? I've tried googling for one, but couldn't find any.

Thanks



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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
#pragma warning(disable: 4996)

#include <cstdlib>
#include <iostream> 
#include <string>
#include <cmath> 
#include <math.h>
#include <algorithm>

using namespace std;

template<class T>
int binarySearch(T a[], T keyVal, int lowVal, int highVal);

int main()
{
	int i = 0;
	int nNumber;
	int finalIndex;

	int a[10] = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 };
	string b[5] = { "apples", "oranges", "peaches", "strawberries", "watermelons" };
	string c[5] = { "apples", "apricots", "morning dew" };

	cout << "Integer test array contains: ";

	for (int i = 0; i < 10; i++)
	{
		cout << a[i];
	}

	int result;

	for (int key = -3; key < 5; key++) 
	{
		result = binarySearch(a, key, 0, finalIndex);

			if(result >= 0)
				cout << key << " is at index " << result;
			else
				cout << key << " is not in the array!";
	}

	finalIndex = 4;

	cout << "String test array contains: ";
	for (int i = 0; i < 5; i++)
	{
		cout << b[i];
	}

	for (int i = 0; i < 3; i++)
	{
		string currentItem = c[i];
		result = binarySearch(b, currentItem, 0, finalIndex);
		if (result >= 0)
			cout << currentItem << " is at index " << result;
		else
			cout << currentItem << " is not in the array ";
	}

	//need this so the DOS window doesn't close
	system("pause");
	return 0;
}

template<class T>
int binarySearch(T a[], T keyVal, int lowVal, int highVal)
{
	int result = 0;
	int midVal = 0;

	while (lowVal <= highVal)
	{
		midVal = (lowVal + highVal) / 2;

		result = midVal;

		if (strcmp(a[midVal], keyVal) < 0)
		{
			lowVal = midVal + 1;
		}
		else if (strcmp(a[midVal], keyVal) > 0)
		{
			highVal = midVal - 1;
		}
		else
		{
			return midVal;
		}
	}

	return -1;
}



Last edited on
mutexe (2372)
but I can't figure out a method to compare the two strings

May i ask, if you're always expecting a string, why is your keyVal defined as a generic parameter? That's implying it might be something other than a string?
cmt9000 (13)
Right, I was wrong. I guess I need a way to compare the two positions?

Maybe I can just do:

1
2
3
 
 if ( a[midVal] < keyVal) ...

 if ( a[midVal > keyVal) ....


Thanks for pointing that out!

Last edited on
Topic archived. No new replies allowed.