C++

Forum

 
Using the same binary search algorithm twice, need to differentiate between returning an in-between number and a found number

keanedawg (181)
Hi guys, I have a school assignment that requests I'm not being redundant with my binary search algorithm (meaning I don't use a binary search algorithm twice). The problem is I need my function to do two separate things. The first thing it needs to do is find an index value within an array AKA a find() function. This find function returns an index value. The second thing it needs to do, is find a value in between two numbers, so I can insert the number in proper order (between two values). The problem is that I made my function do one but not the other, and I really am not sure how I could could make it do both. Currently, it only can find an index value but it can't find a value in between. This is unusual and perhaps there really isn't a good solution. Any thoughts appreciated. 


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
 

// Search algorithm
  template <class T>
int Set<T>::findIndex(T element){

	//int testingArray[9] = { 2, 3, 6, 7, 9, 12, 15, 20, 102 };
	//int testingElement = SetSize; // testing value

	int iFirst = 0;
	int iLast = SetSize;
	int iMidElement = iLast / 2;

	if (SetSize == 0){
		return -1;
	}


	while (iFirst <= iLast){
		iMidElement = (iFirst + iLast) / 2;
		}
		if (ElementArray[iMidElement] > element){
			iLast = iMidElement - 1;
		}
		if (ElementArray[iMidElement] < element){
			iFirst = iMidElement + 1;
		}
		if (ElementArray[iMidElement] == element){
			return iMidElement;
		}
	}
	return -1;
}

// Function I want to use the algorithm with

template <class T>
void Set<T>::insert(T nextElement){
	int i = findIndex(nextElement);
	if (i != -1){
		return;
	}
	try{
		if (SetCapacity == 0){
			this->ElementArray = this->reallocate(1);
		}
		else if (SetSize == SetCapacity){
			this->ElementArray = this->reallocate(SetCapacity * 2);
		}
	}
	catch (bad_alloc){
		cerr << "ERROR: Unable to allocate a new buffer for Vector\n";
	}

///////////////////////////////////////////////////////////////
// THIS IS WHERE THE FUNCTION SHOULD BE CALLED, BUT I'M NOT SURE HOW
///////////////////////////////////////////////////////////////

	SetSize++;
	return;
}


// Find function. This part is already complete.

template <class T>
SetIterator<T> Set<T>::find(T element){
	
	int i = findIndex(element);
	
	if (i >= 0){
		return ElementArray + i;
	}
	else{
		return end();
	}
}
cire (8284)
Perhaps seeing a description of std::lower_bound will help:

http://en.cppreference.com/w/cpp/algorithm/lower_bound
Topic archived. No new replies allowed.