blob: d84401f263b1f8ae4681b221c3dc60d1566b24eb (
plain)
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
|
#include "IntOrderedArray.h"
#include <iostream>
IntOrderedArray::IntOrderedArray() {
}
IntOrderedArray::~IntOrderedArray() {
}
void IntOrderedArray::exploreBinarySearch(int searchKey) const {
int lowerBound = 0;
int upperBound = _collectionSize - 1;
int curIn;
while(1) {
curIn = (lowerBound + upperBound ) / 2;
if(_collection[curIn] == searchKey)
return (void) curIn; // found it
else if(lowerBound > upperBound) {
std::cout << "[" << lowerBound << ", " << upperBound << "]" << std::endl;
return (void) _collectionSize; // can’t find it
}
else // divide range
{
if(_collection[curIn] < searchKey)
lowerBound = curIn + 1; // it’s in upper half
else
upperBound = curIn - 1; // it’s in lower half
} // end find()
}
}
/*
* vul hieronder de tabel in voor vraag 3.b
*
* waarde lowerbound upprbound
* ~~~~~~~~~
* 0 [0, -1]
* 2 [1, 0]
* 4 [2, 1]
* 5 [2, 1]
* 23 [6, 5]
* 26 [6, 5]
* 30 [7, 6]
*/
/*
* formuleer hieronder het antwoord op vraag 3.c
*
* in een ideale wereld waar alle array's alle elementen bevatten die je maar
* zou willen zoeken zou de index van het nummer dat je zoekt tussen upperBound
* en lowerBound liggen, e.g. "4" zou tussen 3 en 6 liggen met index 1 en 2.
*/
int IntOrderedArray::getLastElementSmallerOrEqualTo(int) const {
return -1;
}
void IntOrderedArray::moveElementsOnePositionToRight(int) {
// deze code wordt nergens gebruikt(?)
}
int IntOrderedArray::quickInsert(int value) {
int i;
// find insert index
for (i = 0; i < _collectionSize; i++) {
if (_collection[i] > value) break;
}
// shift elements
for (int k = _collectionSize; k >= i; k--) {
if (k == 0) continue;
_collection[k] = _collection[k-1];
}
_collectionSize++;
_collection[i] = value;
return i;
}
void IntOrderedArray::showAll() const {
for (unsigned i = 0; i < _collectionSize; i++) {
printf("%02d: %d\n", i, _collection[i]);
}
}
|