//Программа иллюстрирует
// статистический алгоритм поиска
# include < iostream.h>
# include < iomanip.h>
const int MAX.ELEMS =10;
const int NOT_FOUND = -1;
const i nt TRUE = 1;
const int FALSE = 0;
class myArray
{
public:
myArray(int fInitVal = 0);
int& operator[](int nlndex)
{ return m_nArray[nlndex]; }
void show(const char* pszMsg = "",
const int nNuinElems = MAX_ELEMS,
const int bOneLine =1);
int statSearch(int nKey,
int nLast = MAX_ELEMS - 1,
int nFirst = 0);
int getNumCompare()
{ return m_nNumCompare; }
protected:
int m_nArray[MAX_ELEMS];
int m_nNumCompare;
};
myArray::myArray(int fInitVal)
{
for (int i = 0; i < MAX_ELEMS; i++)
m_nArray[ i ] = fInitVal;
}
void myArray: :show(const char* psгMsg,
const int nNumElems,
const int bOneLine)
{
cout < < " pszMsg;
if (bOneLine) {
for (int i = 0; i < nNumElems; i++)
cout < < m_nAr ray [ i ] < < ;
cout < < end I;
}
else {
for (int i = 0; i < nNumElems; i++)
cout < < m_nArray[ i ] < < end I;
cout < < end I;
}
}
int myArray::statSearch(int nKey, int nLast, intnFirst)
int nNumElems, rn, i, j. k, nCount, nShift;
int notFound = TRUE;
if (nFirst > nLast ;i nFirst >= MAX_ELEMS) return NOT_FOUND;
nNumElems = nLast - nFirst + 1:
m = nNumElems / 2;
nCount = m;
m_nNumCompare = 0;
// число nNumElems нечетное?
if ((nNumElems % 2) > 0) {
m_nNumCompare++;
// проверяем средний элемент, если число элементов нечетное
if (m_nArray[m] == пКеу) {
nKey = m_nArray[m];
return m;
}
nShift = 1;
}
else
nShift = 0;
k = 2 * m + nShift;
// искать вокруг среднего значения
while (notFound && nCount > 0) {
// искать выше средины
J = k - nCount;
m_nNuinCompare++;
// m_nArray[ j ] совпадает с аргументом поиска?
if (m_Аггау[ j ] == nKey) {
// сохранить индекс найденного элемента в k
k=j;
notFound = FALSE;
}
// элемент все еще не найден
if (notFound) {
// искать ниже медианы а также
// уменьшаем nCount
i = nCount-- - 1;
m_nNuinConipare++;
// m_nArray[i] совпадает с аргументом поиска?
if (m_nArray[i] == nKey) {
// сохранить индекс найденного элемента в k
k = i;
notFound = FALSE;
}
}
}
return (notFound) ? NOT_FOUND : k;
}
niain()
{
int j;
int nArr[MAX ELEMS] = { 23, 45, 89, 74, 51, 18, 87, 63, 36, 38 }:
myArray Array;
fог (int i = 0; i < MAX_ELEMS; i++)
Array[i] = nArr[i];
Array.show("Array is: ");
for (i=0; i < MAX_ELEMS; i+=3){
cout < < "Searching for < < nArr[i];
j = Array.statSearch(nArr[i]);
if (j != NOT_FOUND)
cout < < " found match at index"
< < j < < " (" < < Array.getNumCompare()
< < " comparisons)" < < end I;
else
cout < < " found no match\n";
}
return 0;
}
Вывод программы
Array is: 23 45 89 74 51 18 87 63 36 38
Searching for 23 found match at index 0 (10 comparisons)
Searching for 74 found match at index 3 (4 comparisons)
Searching for 87 found match at index 6 (3 comparisons)
Searching for 38 found match at index 9 (9 comparisons)
Содержание