بـــــســـــم الـــــلـــــه

بحث الحَزْر طريقة للبحث عن قيمة وسط جدول.

طـريـقـة الـبـحـث

بحث الحزر يشأن التالي:

1. يقرأ أكبر عدد و اصغر عدد في الجدول في أول الجدول و آخره
2. يحسب المكان المنتظر للعدد المفتش عنه و هو
   (العدد_المفتش_عنه - أصغر_عدد) \ (أكبر_عدد - أصغر_عدد) * (طول_جدول - 1)
3. إن كان المكان يحوي العدد المبغي تم البحث
4. يقسم الجدول إلى جدولين في ذلك المكان و يعاد البحث بنفس الطريقة في أحد الجدولين الممكن وجود القيمة فيه
5. إن بلغ طول الجدول واحدا ينتهي البحث دون وجود القيمة

أوقـات بحث في جـداول أعـداد

و الجدول التالي يبين الوقت المقضي في البحث على شكل نسبة مئوية من وقت البحث السريع أي كويك_سارتش أو بيسارتش كما تسمى في ليبسي.

طريقة البحث	النسبة المئوية للوقت المقضي مقارنة مع البحث السريع
	ألف عدد	10 آلاف عدد	10 آلاف ألف عدد
بحث حزر مع تمرير -O2 لجيسيسي	116.2%	91.5%	56.9%
بحث حزر مع تمرير -O3 لجيسيسي	202.2%	167.5%	102%
بحث حزر مع تمرير -O0 لجيسيسي	126.3%	100.5%	66.5%

ما يحدث مع -O3 أن وقت بحث الحزر يبقى مقاربا لوقت عمله مع -O2 لكن وقت بيسارتش يقل للنصف تقريبا ربما لأن جيسيسي يتفطن أن القيم التي يبحث عنها لا يعمل بها.

البحث عن رُفُؤٍ أي ستراكتير

طريقة البحث المذكورة آنفا تصلح لجدول أعداد أو جدول رُفُؤٍ أي ستراكتير مفتاح ترتيبه قيمة بسيطة مثل عدد أو أعداد مجزأة مفردة أي سينغل و أعداد مجزأة ضعف أي دابل.
لترتيب رَفِيئة أي ستراكتير يعمل بالأطوار و ثمة عندئذ رفيئة طور تمرر و دالة نقل إلى الطور التالي و دالة ترجع نوع قيمة الطور الراهن هل هي عدد أم مفرد أم ضعف. و هاتان الدالتان تمرران أيضا مثل الطور.
و تمرر آخر قيمة إلى دَالَةِ الانتقال للطور التالي ليعلم إن كان يرتب نسقا في ذلك الوقت إن كان بلغ نهاية النسق أم لا.
و الطور هنا يسجل أي عضو من الرفيئة و أي قسم من ذلك العضو يتم به البحث.

أوقات بحث جداول رُفُؤٍ

الجدول التالي يذكر نسب أوقات بحث حزر عن رُفُؤٍ أي ستراكتر. كل رفيئة تحوي عددا و مُؤَشِّرَ نَسَقٍ و عددا مُجَزَّأً أي فلوت و يقارن بالأعداد فإن تساوت يقارن بحروف الأنساق و إن تساوت الأنساق يقارن بالمجزئين. و بحث حزر هنا يعمل بالأطوار.

طريقة البحث	النسبة المئوية للوقت المقضي مقارنة مع البحث السريع
	ألف عدد	10 آلاف عدد	10 آلاف ألف عدد
بحث حزر مع -O2 لجيسيسي	339.9%	343.2%	291.1%
بحث حزر مع -O0 لجيسيسي	522.5%	554.5%	495.3%

الأعداد في الجدول السابق تحوي فقط 21 عددا مختلفا و 31 قيمة مجزأ. و الأنساق أطوالها بين 1 و 11 و تحوي حروفا من بين 7 حروف ممكنة فقط. و هذا يُعْقِبُ تكرارا فلا يرتب الجدول بأول عدد فقط.

رُقُـم بحث حـزر

#إنكلود <أسارت.ه>

#دفاين ترو ١
#دفاين فالس ٠
#دفاين بوول شار

#دفاين نوول ٠

#دفاين أند &&
#دفاين أور ||
#دفاين نوت !

#دفاين إك ==
#دفاين نإ !=
#دفاين غذ >
#دفاين غإ >=
#دفاين لذ <
#دفاين لإ <=

#دفاين أكد أسارت

ستركت لث_طور_س {
   إنت طور؛
   إنت قسم؛
}؛

ينيون لث_صحيح_و_مفرد_و {
   إنت صحيح؛
   فلوت مفرد؛
}؛

ينيون لث_طوال_و_ضعف_و {
   أنسايند لونغ لونغ طوال_وافر؛
   دابل ضعف؛
}؛

#دفاين خ_قاسم_ب (٤)
#دفاين خ_حد_قسمة_ب (خ_قاسم_ب >> ١)

كونست ستركت لث_طور_س لث_طور_صفر = {٠}؛

\* لث_جد {{{ *\
إنت لث_جد(فويد *جدول، إنت عدة_جدول، إنت طول_واحد، إنت (*قيمة)(فويد*)، إنت غاية)
{
   \* تبحث عن رفيئه أو عدد قيمته سي غاية وسط جدول
    * جدول مرتب الأكبر فالأكبر *\
   فويد *بدء = نوول؛
   إنت عدة_بدء = ٠؛
   إنت قيمة_بدء = ٠؛
   إنت قيمة_نهية = ٠؛
   إنت قيمة_حزرت = ٠؛
   فويد *حرف_حزر = نوول؛
   إنت رتبة_حزرت = ٠؛
   إنت مسافة = ٠؛

   أكد(جدول)؛
   أكد(١ لإ عدة_جدول)؛
   أكد(١ لإ طول_واحد)؛
   أكد(قيمة)؛
   أكد(قيمة نإ جدول)؛

   بدء = جدول؛
   عدة_بدء = عدة_جدول؛
   قيمة_بدء = قيمة(بدء)؛
   قيمة_نهية = قيمة(بدء + (عدة_بدء - ١) * طول_واحد)؛

   إف (غاية > قيمة_بدء أور غاية < قيمة_نهية)
      رتورن -١؛
   إف (غاية إك قيمة_بدء)
      رتورن ٠؛
   إف (غاية إك قيمة_نهية)
      رتورن عدة_بدء - ١؛
بعد_فحص_نهية:
   إف (٢ غإ عدة_بدء)
      رتورن -١؛
   رتبة_حزرت = ((لونغ لونغ)قيمة_بدء - غاية) * عدة_بدء
               \ ((لونغ لونغ)قيمة_بدء - قيمة_نهية)؛
   أكد(٠ <= رتبة_حزرت)؛
   أكد(عدة_بدء > رتبة_حزرت)؛
   إف (٠ إك رتبة_حزرت)
      رتبة_حزرت++؛
   آلس إف ((عدة_بدء - ١) == رتبة_حزرت)
      رتبة_حزرت--؛

   حرف_حزر = بدء + رتبة_حزرت * طول_واحد؛
   قيمة_حزرت = قيمة(حرف_حزر)؛
   إف (غاية إك قيمة_حزرت)
      رتورن رتبة_حزرت + مسافة؛
   آلس إف (غاية > قيمة_حزرت) {
      عدة_بدء = رتبة_حزرت + ١؛
      قيمة_نهية = قيمة_حزرت؛
      غوتو بعد_فحص_نهية؛
   }
   آلس {
      عدة_بدء -= رتبة_حزرت؛
      بدء = حرف_حزر؛
      مسافة += رتبة_حزرت؛
      قيمة_بدء = قيمة_حزرت؛
      غوتو بعد_فحص_نهية؛
   }
}
\* }}} *\

\* خ_قارن_طورين {{{ *\
إنت خ_قارن_طورين(ستركت لث_طور_س *أول، ستركت لث_طور_س *ثان)
{
   \* ترجع ١ أن كان أول أعمق من ثان و -١ أن العكس و ٠ أن تساويا *\
   أكد(أول)؛
   أكد(ثان)؛
   أكد(-١ < أول->طور)؛
   أكد(-١ < أول->قسم)؛
   أكد(١٠٢٤ > أول->طور)؛
   أكد(-١ < ثان->طور)؛
   أكد(-١ < ثان->قسم)؛
   أكد(١٠٢٤ > ثان->طور)؛

   إف (أول->طور > ثان->طور)
      رتورن ١؛
   إف (أول->طور < ثان->طور)
      رتورن -١؛
   إف (أول->قسم > ثان->قسم)
      رتورن ١؛
   إف (أول->قسم < ثان->قسم)
      رتورن -١؛
   رتورن ٠؛
}
\* }}} *\

\* لث_جد_بطور {{{ *\
إنت لث_جد_بطور(فويد *جدول، إنت عدة_جدول، إنت طول_واحد،
               إنت (*قيمة)(فويد*، ستركت لث_طور_س)، فويد *غاية،
               بوول (*نوع)(ستركت لث_طور_س)،
               بوول (*تال)(ستركت لث_طور_س*، إنت أخر_قيمة))
{
   \* تبحث عن رفيئه أو عدد قيمته سي غاية وسط جدول
    * جدول مرتب الأكبر فالأكبر *\
   \* أخطاء_ب: ٣ *\
   فويد *بدء = نوول؛
   فويد *نهية = نوول؛
   إنت عدة_بدء = ٠؛
   إنت عدة_بدء_مقسومة = ٠؛
   إنت قيمة_بدء = ٠؛
   إنت قيمة_نهية = ٠؛
   إنت ظل_قيمة_بدء = ٠؛
   إنت ظل_قيمة_نهية = ٠؛
   إنت قيمة_حزرت = ٠؛
   إنت قيمة_غاية = ٠؛
   فويد *مكان_حزر = نوول؛
   إنت رتبة_حزرت = ٠؛
   ستركت لث_طور_س طور_بدء = لث_طور_صفر؛
   ستركت لث_طور_س طور_نهية = لث_طور_صفر؛
   ستركت لث_طور_س طور_حزر = لث_طور_صفر؛
   إنت مسافة = ٠؛
   بوول قدم_طور = فالس؛
   إنت رقط = ٠؛ \* رجعى مقارنة طورين *\

   أكد(جدول)؛
   أكد(١ لإ عدة_جدول)؛
   أكد(١ لإ طول_واحد)؛
   أكد(قيمة)؛
   أكد(قيمة نإ جدول)؛
   أكد(غاية)؛
   أكد(نوع)؛
   أكد(تال)؛
   أكد((فويد*)قيمة نإ نوع)؛
   أكد((فويد*)قيمة نإ تال)؛
   أكد((فويد*)تال نإ نوع)؛

   بدء = جدول؛
   عدة_بدء = عدة_جدول؛
   قيمة_بدء = قيمة(بدء، طور_بدء)؛
   نهية = بدء + (عدة_بدء - ١) * طول_واحد؛
   قيمة_نهية = قيمة(نهية، طور_نهية)؛
   قيمة_غاية = قيمة(غاية، طور_حزر)؛

   إف (قيمة_غاية > قيمة_بدء أور قيمة_غاية < قيمة_نهية)
      رتورن -١؛

   إف (قيمة_غاية إك قيمة_بدء) {
فحص_مساواة_بدء:
      قدم_طور = تال(&طور_بدء، قيمة_بدء)؛
      إف (فالس == قدم_طور)
         رتورن ٠؛
      آلس {
         قيمة_بدء = قيمة(بدء، طور_بدء)؛
         طور_حزر = طور_بدء؛
         قيمة_غاية = قيمة(غاية، طور_حزر)؛

         إف (قيمة_غاية > قيمة_بدء)
            رتورن -١؛
         إف (قيمة_غاية إك قيمة_بدء)
            غوتو فحص_مساواة_بدء؛
      }
   }

   إف (خ_قارن_طورين(&طور_حزر، &طور_نهية)) {
      طور_حزر = طور_نهية؛
      قيمة_غاية = قيمة(غاية، طور_حزر)؛
   }
   إف (قيمة_غاية إك قيمة_نهية) {
فحص_مساواة_نهية:
      قدم_طور = تال(&طور_نهية، قيمة_نهية)؛
      إف (فالس == قدم_طور)
         رتورن عدة_بدء - ١؛
      آلس {
         قيمة_نهية = قيمة(نهية، طور_نهية)؛
         طور_حزر = طور_نهية؛
         قيمة_غاية = قيمة(غاية، طور_حزر)؛
         إف (قيمة_غاية < قيمة_نهية)
            رتورن -١؛
         إف (قيمة_غاية إك قيمة_نهية)
            غوتو فحص_مساواة_نهية؛
      }
   }
بعد_فحص_نهية:

   إف (٢ غإ عدة_بدء)
      رتورن -١؛

   رقط = خ_قارن_طورين(&طور_بدء، &طور_نهية)؛
   إف (١ == رقط) {
      إف (خ_قارن_طورين(&طور_حزر، &طور_نهية)) {
         طور_حزر = طور_نهية؛
         قيمة_غاية = قيمة(غاية، طور_حزر)؛
      }
      ظل_قيمة_بدء = قيمة(بدء، طور_حزر)؛

      رتبة_حزرت = ((لونغ لونغ)ظل_قيمة_بدء - قيمة_غاية) * عدة_بدء
                  \ ((لونغ لونغ)ظل_قيمة_بدء - قيمة_نهية)؛
   }
   آلس {
      إف (خ_قارن_طورين(&طور_حزر، &طور_بدء)) {
         طور_حزر = طور_بدء؛
         قيمة_غاية = قيمة(غاية، طور_حزر)؛
      }
      إف (-١ == رقط) {
         ظل_قيمة_نهية = قيمة(نهية، طور_حزر)؛

         رتبة_حزرت = ((لونغ لونغ)قيمة_بدء - قيمة_غاية) * عدة_بدء
                     \ ((لونغ لونغ)قيمة_بدء - ظل_قيمة_نهية)؛
      }
      آلس
         رتبة_حزرت = ((لونغ لونغ)قيمة_بدء - قيمة_غاية) * عدة_بدء
                     \ ((لونغ لونغ)قيمة_بدء - قيمة_نهية)؛
   }

   أكد(٠ <= رتبة_حزرت)؛
   أكد(عدة_بدء غإ رتبة_حزرت)؛

   عدة_بدء_مقسومة = عدة_بدء \ خ_قاسم_ب؛
   إف (رتبة_حزرت لإ عدة_بدء_مقسومة) {
      إف (خ_حد_قسمة_ب لإ عدة_بدء)
         رتبة_حزرت = عدة_بدء_مقسومة؛
      آلس
         رتبة_حزرت++؛
   }
   آلس إف (رتبة_حزرت غإ (عدة_بدء - ١ - عدة_بدء_مقسومة)) {
      إف (خ_حد_قسمة_ب لإ عدة_بدء)
         رتبة_حزرت = عدة_بدء - عدة_بدء_مقسومة؛
      آلس {
         إف ((عدة_بدء - ١) == رتبة_حزرت)
            رتبة_حزرت--؛
         آلس
            \* عدة_بدء إك رتبة_حزرت *\
            رتبة_حزرت -= ٢؛
      }
   }

   مكان_حزر = بدء + رتبة_حزرت * طول_واحد؛
   قيمة_حزرت = قيمة(مكان_حزر، طور_حزر)؛
   إف (قيمة_غاية إك قيمة_حزرت) {
فحص_مساواة_حزر:
      قدم_طور = تال(&طور_حزر، قيمة_حزرت)؛
      إف (فالس == قدم_طور)
         رتورن رتبة_حزرت + مسافة؛
      آلس {
         قيمة_حزرت = قيمة(مكان_حزر، طور_حزر)؛
         قيمة_غاية = قيمة(غاية، طور_حزر)؛
         إف (قيمة_غاية إك قيمة_حزرت)
            غوتو فحص_مساواة_حزر؛
      }
   }
   إف (قيمة_غاية > قيمة_حزرت) {
      عدة_بدء = رتبة_حزرت + ١؛
      نهية = مكان_حزر؛
      قيمة_نهية = قيمة_حزرت؛
      طور_نهية = طور_حزر؛
      غوتو بعد_فحص_نهية؛
   }
   آلس {
      أكد(قيمة_غاية < قيمة_حزرت)؛
      عدة_بدء -= رتبة_حزرت؛
      بدء = مكان_حزر؛
      مسافة += رتبة_حزرت؛
      قيمة_بدء = قيمة_حزرت؛
      طور_بدء = طور_حزر؛
      غوتو بعد_فحص_نهية؛
   }
}
\* }}} *\

ستركت ر_عضو_س {
   إنت عدد؛
   شار *نسق؛
   فلوت مجزأ؛
}؛

\* ر_نوع_طور_عدد {{{ *\
بوول ر_نوع_طور_عدد(ستركت لث_طور_س  طور)
{
   \* ترجع صوابا أن كان نوع الطور الحاضر عددا *\
   أكد(-١ < طور.طور)؛
   أكد(٢ >= طور.طور)؛
   أكد(-١ < طور.قسم)؛
   أكد(١ != طور.طور ؟ ٠ == طور.قسم : ١)؛

   رتورن (٢ == طور.طور) ؟ فالس : ترو؛
}
\* }}} *\
\* ر_طور_تال {{{ *\
بوول ر_طور_تال(ستركت لث_طور_س *طور، إنت قيمة)
{
   أكد(طور)؛
   أكد(-١ < طور->طور)؛
   أكد(٢ >= طور->طور)؛
   أكد(-١ < طور->قسم)؛
   أكد(١ != طور->طور ؟ ٠ == طور->قسم : ١)؛

   إف (٠ == طور->طور) {
      طور->طور = ١؛
      رتورن ترو؛
   }
   آلس إف (١ == طور->طور) {
      إف (قيمة)
         طور->قسم++؛
      آلس {
         طور->طور = ٢؛
       طور->قسم = ٠؛
      }
      رتورن ترو؛
   }
   آلس
      رتورن فالس؛
}
\* }}} *\
\* ر_قيمة_طور {{{ *\
إنت ر_قيمة_طور(فويد *عضو، ستركت لث_طور_س طور)
{
   \* أخطاء_ب: ١ *\
   ينيون لث_صحيح_و_مفرد_و صف = {٠}؛
   أكد(عضو)؛
   أكد(-١ < طور.طور)؛
   أكد(٢ >= طور.طور)؛
   أكد(-١ < طور.قسم)؛
   أكد(١ != طور.طور ؟ ٠ == طور.قسم : ١)؛

   إف (٠ == طور.طور)
      رتورن ((ستركت ر_عضو_س*)عضو)->عدد؛
   آلس إف (١ == طور.طور)
      رتورن ((ستركت ر_عضو_س*)عضو)->نسق[طور.قسم]؛
   آلس {
      صف.مفرد = ((ستركت ر_عضو_س*)عضو)->مجزأ؛
      رتورن صف.صحيح؛
   }
}
\* }}} *\

\* ر_قارن {{{ *\
إنت ر_قارن(ستركت ر_عضو_س *أول، ستركت ر_عضو_س *ثان)
{
   \* أخطاء_ب: ١ *\
   إنت رجعى_نسق = ٠؛

   أكد(أول)؛
   أكد(ثان)؛
   إف (أول->عدد > ثان->عدد)
      رتورن -١؛
   آلس إف (أول->عدد < ثان->عدد)
      رتورن ١؛
   رجعى_نسق = ستركمب(أول->نسق، ثان->نسق)؛
   إف (رجعى_نسق)
      رتورن رجعى_نسق > ٠ ؟ -١ : ١؛
   إف (أول->مجزأ > ثان->مجزأ)
      رتورن -١؛
   آلس إف (أول->مجزأ < ثان->مجزأ)
      رتورن ١؛
   آلس
      رتورن ٠؛
}
\* }}} *\

النسخة الراهنة لدالة بحث حزر من غير طور لا يعالج تكرر نفس القيم في الجدول بكفاءة خلاف دالة البحث بالأطوار. و عند وجود تكرار يصير زمن البحث مضارعا لعِدَّةِ الجدول أي ض(ع) أي O(n)‎.
و لذلك لا ينبغي العمل بها في برنامج تجاري قبل تصويب ذلك النقص.

لث_جد_بطور تعالج فقط أعدادا و أنساقا أي سترينغ و أعدادا مجزأة مفردة أي فلوت. و عَطِيَّة نوع أي أرغيومانت التي تمرر للدالة يتم تجاهلها. وهي موجودة لأن دالة البحث بالأطوار عند كتابتها تم نقل معاطي ترتيب حزر بأطوار إليها و نسيت إزالتها. و ربما إن زيدت معالجة عدد مجزإ ضعف أي دابل يعمل بها.

دالة ر_قارن تمرر لبيسارتش و ليست ل لث_جد_بطور.