عمل جستجو يکی از مهمترين وظايف برنامه های کامپيوتری می باشد . به عنوان مثال دفتر تلفنی را در نظر بگيريد که به دنبال نام فردی در آن می گرديم و يا جستجوی نام يک دانشجو در ليست دانشجويان کلاس . در اين مبحث دو روش جستجو را مورد بررسی قرار می دهيم . يک روش جستجوی خطی است که معمولاً در آرايه های نا مرتب مورد استفاده قرار می گيرد و روش ديگر جستجوی دو دويی می باشد که در آرايه های مرتب از اين شيوه می توانيم استفاده کنيم .

   در روش جستجوی خطی ، عنصر مورد جستجو با هر يک از عناصر آرايه مقايسه می شود ، چنانچه دو عنصر برابر بودند ، عمل جستجو به پايان می رسد و انديس عنصر برگردانده می شود و گرنه مقايسه با عنصر بعدی آرايه انجام می پذيرد . از آنجا که عناصر آرايه نا مرتب می باشند عنصر مورد جستجو در هر کجای آرايه می تواند باشد لذا عمل مقايسه تا يافتن عنصر مورد نظر و يا رسيدن به انتهای آرايه يعنی جستجو در همه عناصر آرايه ادامه می يابد . برنامه زير نمونه ای از جستجوی خطی در آرايه می باشد :

#include 
 
int linearSearch(const int [], int, int );
 
void main()
{
   const int arraySize = 7;
   int a[ arraySize ]={2,6,4,3,12,10,5};
   int searchKey;
 
   cout << "Enter integer search key: ";
   cin >> searchKey;
 
   int element=linearSearch(a, searchKey, arraySize);
 
   if ( element != -1 )
      cout << "Found value in element " 
           << element << endl;
   else
      cout << "Value not found" << endl;
 
}
 
int linearSearch( const int array[],
                  int key, int sizeOfArray )
{
   for ( int j = 0; j < sizeOfArray; j++ )
 
   if ( array[ j ] == key )
      return j;
 
   return -1;
}

خروجی برنامه فوق به صورت زير می باشد :

Enter integer search key: 12
Found value in element 4

    روش جستجوی دو دويی در آرايه های مرتب شده قابل استفاده می باشد و از سرعت بالايی برخوردار می باشد . در اين الگوريتم ، در هر بار مقايسه ، نيمی از عناصر آرايه حذف می شوند . الگوريتم عنصر ميانی آرايه را می يابد و آن را با عنصر مورد جستجو، مقايسه می کند . اگر برابر بودند ، جستجو به پايان رسيده و انديس عنصر برگردانده می شود ، در غير اين صورت عمل جستجو روی نيمی از عناصر انجام می گيرد . اگر عنصر مورد جستجو کوچکتر از عنصر ميانی باشد ، جستجو روی نيمه اول آرايه صورت می پذيرد ، در غير اين صورت نيمه دوم آرايه جستجو می شود . اين جستجوی جديد روی زير آرايه طبق الگوريتم جستجو روی آرايه اصلی انجام می شود يعنی عنصر ميانی زير آرايه يافته می شود و با عنصر مورد جستجو مقايسه می گردد ، اگر برابر نباشند زير آرايه مجدداً نصف می شود و در هر بار جستجو زير آرايه ها کوچکتر می گردند . عمل جستجو تا يافتن عنصر مورد نظر( يعنی برابر بودن عنصر مورد جستجو با عنصر ميانی يکی از زير آرايه ها ) و يا نيافتن عنصر مورد نظر ( برابر نبودن عنصر مورد جستجو با عنصر زير آرايه ای شامل تنها يک عنصر ) ادامه می يابد . برنامه زير نمونه ای از جستجوی دو دويی در آرايه مرتب می باشد .

#include 
 
int binarySearch( const int [], int, int);
 
void main()
{
  const int arraySize = 15;
  int a[ arraySize ]={0,2,4,6,8,10,12,14,
                      16,18,20,22,24,26,28};
  int key;
 
  cout << "Enter a number between 0 and 28: ";
  cin >> key;
 
  int result =
      binarySearch( a, arraySize, key);
 
  if ( result != -1 )
    cout << '\n' << key << " found in array element "
         << result << endl;
  else
    cout << '\n' << key << " not found" << endl;
}
 
int binarySearch( const int b[],
                  int arraySize ,
                  int searchKey )
{
  int middle,low=0,high=arraySize - 1;
 
  while ( low <= high )
  {
    middle = ( low + high ) / 2;
    if ( searchKey < b[ middle ] )
      high = middle - 1;
    else
      if ( searchKey > b[ middle ] )
        low = middle + 1;
      else return middle;
  }
 
  return -1;
}

   خروجی برنامه فوق به صورت زير می باشد :

Enter a number between 0 and 28: 8
 
8 found in array element 4