جستجو در آرایه ها

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

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

#include <iostream.h>

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;

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

#include <iostream.h>

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;