مقالات و جزوه های درسی رشته کامپیوتر

8- الگوريتم جستجوي دودويي

در روش جستجوي دودويي به يک آرايۀ مرتب نياز است.

 هنگام جستجو آرايه از وسط به دو بخش بالايي و پاييني تقسيم مي‌شود.

مقدار مورد جستجو با آخرين عنصر بخش پاييني مقايسه مي‌شود.

 اگر اين عنصر کوچک‌تر از مقدار جستجو بود، مورد جستجو در بخش پاييني وجود ندارد و بايد در بخش بالايي به دنبال آن گشت.

 

دوباره بخش بالايي به دو بخش تقسيم مي‌گردد و گام‌هاي بالا تکرار مي‌شود.

 سرانجام محدودۀ جستجو به يک عنصر محدود مي‌شود که يا آن عنصر با مورد جستجو برابر است و عنصر مذکور يافت شده و يا اين که آن عنصر با مورد جستجو برابر نيست و لذا مورد جستجو در آرايه وجود ندارد.

 اين روش پيچيده‌تر از روش جستجوي خطي است اما در عوض بسيار سريع‌تر به جواب مي‌رسيم.

 

مثال‌ 14-6 جستجوي دودويي

برنامۀ آزمون زير با برنامۀ آزمون مثال 12-6 يکي است اما تابعي که در زير آمده از روش جستجوي دودويي براي يافتن مقدار درون آرايه استفاده مي‌کند:

int index(int, int[],int);

int main()

{  int a[] = { 22, 33, 44, 55, 66, 77, 88 };

   cout << "index(44,a,7) = " << index(44,a,7) << endl;

   cout << "index(60,a,7) = " << index(60,a,7) << endl;

}

int index(int x, int a[], int n)

{  // PRECONDITION: a[0] <= a[1] <= ... <= a[n-1];

   // binary search:

   int lo=0, hi=n-1, i;

   while (lo <= hi)

   {  i = (lo + hi)/2;          // the average of lo and hi

      if (a[i] == x) return i;

      if (a[i] < x) lo = i+1;   // continue search in a[i+1..hi]

      else hi = i-1;            // continue search in a[0..i-1]

   }

   return n;                   // x was not found in a[0..n-1]

}

خروجي:

index(44,a,7) = 2

index(60,a,7) = 7

براي اين که بفهميم تابع چطور کار مي‌کند، فراخواني index(44,a,7) را دنبال مي‌کنيم.

 وقتي حلقه شروع مي‌شود، x=44 و n=7 و lo=0 و hi=6 است.

 ابتدا i مقدار (0+6)/2 = 3 را مي‌گيرد.پس عنصر a[i] عنصر وسط آرايۀ a[0..6] است. مقدار a[3] برابر با 55 است که از مقدار x بزرگ‌تر است. پس x در نيمۀ بالايي نيست و جستجو در نيمۀ پاييني ادامه مي‌يابد. لذا hi با i-1 يعني 2 مقداردهي مي‌شود و حلقه تکرار مي‌گردد.

 

حالا hi=2 و lo=0 است و دوباره عنصر وسط آرايۀ a[0..2] يعني a[1] با x مقايسه مي‌شود. a[1] برابر با 33 است که کوچک‌تر از x مي‌باشد. پس اين دفعه lo برابر با i+1 يعني 2 مي‌شود.

 در سومين دور حلقه، hi=2 و lo=2 است. پس عنصر وسط آرايۀ a[2..2] که همان a[2] است با x مقايسه مي‌شود. a[2] برابر با 44 است که با x برابر است. پس مقدار 2 بازگشت داده مي‌شود؛ يعني x مورد نظر در a[2] وجود دارد.

 

 

حال فراخواني index(60,a,7) را دنبال مي‌کنيم. وقتي حلقه شروع مي‌شود، x=60 و n=7 و lo=0 و hi=6 است. عنصر وسط آرايۀ a[0..6] عنصر a[3]=55 است که از x کوچک‌تر است. پس lo برابر با i+1=4 مي‌شود و حلقه دوباره تکرار مي‌شود. اين دفعه hi=6 و lo=4 است . عنصر وسط آرايۀ a[4..6] عنصر a[5]=77 است که بزرگ‌تر از x مي‌باشد. پس hi به i-1=4 تغيير مي‌يابد و دوباره حلقه تکرار مي‌شود. اين بار hi=4 و lo=4 است و عنصر وسط آرايۀ a[4..4] عنصر a[4]=66 است که بزرگ‌تر از  x  مي‌باشد.   لذا hi به i-1=3 کاهش مي‌يابد.

 

 

 

اکنون شرط حلقه غلط مي‌شود زيرا hi است. بنابراين تابع مقدار 7 را برمي‌گرداند يعني عنصر مورد نظر در آرايه موجود نيست.

 

در تابع فوق هر بار که حلقه تکرار مي‌شود، محدودۀ جستجو 50% کوچک‌تر مي‌شود. در آرايۀ n عنصري، روش جستجوي دودويي حداکثر به   log2 n+1 مقايسه نياز دارد تا به پاسخ برسد.

حال آن که در روش جستجوي خطي به n مقايسه نياز است.

 

 

تفاوتهاي جستجوي دودويي و خطي

 جستجوي دودويي سريع‌تر از جستجوي خطي است.

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

 سومين فرق در اين است که جستجوي دودويي فقط روي آرايه‌هاي مرتب کارايي دارد و اگر آرايه‌اي مرتب نباشد، جستجوي دودويي پاسخ غلط مي‌دهد ولي جستجوي خطي هميشه پاسخ صحيح خواهد داد.

 

* مثال‌ 15-6 مشخص كردن اين كه آيا آرايه مرتب است يا خير

برنامۀ زير يک تابع بولي را آزمايش مي‌کند. اين تابع مشخص مي‌نمايد که آيا آرايۀ داده شده غير نزولي است يا خير:

bool isNondecreasing(int a[], int n);

int main()

{  int a[] = { 22, 44, 66, 88, 44, 66, 55 };

   cout<<"isNondecreasing(a,4) = " << isNondecreasing(a,4)<< endl;

   cout<<"isNondecreasing(a,7) = " << isNondecreasing(a,7) << endl;

}

 

 

bool isNondecreasing(int a[], int n)

{  // returns true iff a[0] <= a[1] <= ... <= a[n-1]:

   for (int i=1; i

      if (a[i]

   return true;

}

 

خروجي:

isNondecreasing(a,4) = 1

isNondecreasing(a,7) = 0

 

اين تابع يک بار کل آرايه را پيمايش کرده و زوج‌هاي a[i-1] و a[i] را مقايسه مي‌کند.

اگر زوجي يافت شود که در آن a[i] باشد، مقدار false را بر مي‌گرداند به اين معني که آرايه مرتب نيست.

 ببينيد که مقادير true و false به شکل اعداد 1 و 0 در خروجي چاپ مي‌شوند زيرا مقادير بولي در حقيقت به شکل اعداد صحيح در حافظه ذخيره مي‌شوند.

 

 

اگر پيش‌شرط مثال 14-6 يعني مرتب بودن آرايه رعايت نشود، جستجوي دودويي پاسخ درستي نمي‌دهد. به اين منظور ابتدا بايد اين پيش‌شرط بررسي شود.

 با استفاده از تابع assert() مي‌توان اجراي يک برنامه را به يک شرط وابسته کرد.

 اين تابع يک آرگومان بولي مي‌پذيرد. اگر مقدار آرگومان false باشد، برنامه را خاتمه داده و موضوع را به سيستم عامل گزارش مي‌کند. اگر مقدار آرگومان true باشد، برنامه بدون تغيير ادامه مي‌يابد.

 تابع asset() در سرفايل تعريف شده است.

 

 

مثال‌ 16-6 استفاده از تابع assert() براي رعايت كردن يك‌ پيش‌شرط

برنامۀ زير نسخۀ بهبوديافته‌اي از تابع search() مثال 14-6 را آزمايش مي‌کند. در اين نسخه، از تابع isNonDecreasing() مثال 15-6 استفاده شده تا مشخص شود آرايه مرتب است يا خير.

نتيجه اين تابع به تابع assert() ارسال مي‌گردد تا اگر آرايه مرتب نباشد برنامه به بيراهه نرود.

 

 

#include     // defines the assert() function

#include    // defines the cout object

using namespace std;

int index(int x, int a[], int n);

int main()

{  int a[] = { 22, 33, 44, 55, 66, 77, 88, 60 };

   cout<<"index(44,a,7) = " << index(44,a,7) << endl;

   cout<<"index(44,a,8) = " << index(44,a,8) << endl;

   cout<<"index(60,a,8) = " << index(60,a,8) << endl;

}

 

bool isNondecreasing(int a[], int n);

int index(int x, int a[], int n)

{  assert(isNondecreasing(a,n));

   int lo=0, hi=n-1, i;

   while (lo <= hi)

   {  i = (lo + hi)/2;

      if (a[i] == x) return i;

      if (a[i] < x) lo = i+1;  

      else hi = i-1;    }

   return n;   

‌‌}

خروجي:

index(44,a,7) = 2

 

آرايۀ a[] که در اين برنامه استفاده شده كاملا مرتب‌ نيست‌ اما هفت‌ عنصر اول‌ آن‌ مرتب‌ است. بنابراين‌ در فراخواني‌index(44,a,7) تابع بولي مقدار true را به assert() ارسال مي‌کند و برنامه ادمه مي‌يابد.

 اما در دومين فراخواني index(44,a,8) باعث مي‌شود که تابع ‌isNondecreasing() مقدار false را به تابع assert() ارسال کند كه در اين صورت برنامه متوقف مي‌شود و ويندوز پنجرۀ هشدار مقابل را نمايش مي‌دهد.

 

9- استفاده از انواع شمارشي در آرايه

انواع‌ شمارشي‌ در جلسه‌ دوم‌ توضيح‌ داده‌ شده‌اند.

 با استفاده از انواع شمارشي نيز مي‌توان آرايه‌ها را پردازش نمود.

 مثال‌ 17-7 شمارش با استفاده از روزهاي هفته

اين‌ برنامه‌ يك‌ آرايه به نام‌ high[] با هفت‌ عنصرازنوعfloat  تعريف‌ مي‌كند كه‌ هر عنصر حداکثر دما در يک روز هفته را نشان مي‌دهد:

int main()

{  enum Day { SUN, MON, TUE, WED, THU, FRI, SAT };

   float high[SAT+1] = {28.6, 29.1, 29.9, 31.3, 30.4, 32.0, 30.7};

   for (int day = SUN; day <= SAT; day++)

   cout << "The high temperature for day " << day << " was "<< high[day] << endl;

}

خروجي:

 

The high temperature for day 0 was 28.6

The high temperature for day 1 was 29.1

The high temperature for day 2 was 29.9

The high temperature for day 3 was 31.3

The high temperature for day 4 was 30.4

The high temperature for day 5 was 32.0

The high temperature for day 6 was 30.7

 

به خاطر بياوريد که انواع شمارشي به شکل مقادير عددي ذخيره مي‌شوند.

 اندازۀ آرايه، SAT+1 است زيرا SAT مقدار صحيح 6 را دارد و آرايه به هفت عنصر نيازمند است. متغير day از نوع int است‌ پس مي‌توان مقادير Day را به آن تخصيص داد. استفاده از انواع شمارشي در برخي از برنامه‌ها باعث مي‌شود که کد برنامه «خود استناد» شود. مثلا در مثال 17-6 کنترل حلقه به شکل

for (int day = SUN; day <= SAT; day++)

باعث مي‌شود که هر بيننده‌اي حلقۀ for بالا را به خوبي درک کند.