//Программа иллюстрирует
// статистический алгоритм поиска	
# 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)

Содержание