جستجوی دو دویی

در آرایه های مرتب شده قابل استفاده می باشد و از سرعت بالایی برخوردار می باشد . در این الگوریتم ، در هر بار مقایسه ، نیمی از عناصر آرایه حذف می شوند .

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

#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;

}

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

Enter a number between 0 and 28: 8