كيفية العثور على آخر عنصر من عناصر المصفوفة الثنائية البحث

Question

في خوارزمية البحث الثنائي ، العليا-لا بد عنصر array.length-1, ثم كيف يمكنني العثور على آخر عنصر من عناصر المصفوفة ؟

إذا كانت الدنيا لا بد العليا متجهة إلى عنصر صفيف من طول 8 6 و 7 على التوالي بعد منتصف عنصر الخروج كما:

المتوسط=(6+7)/2 أي6 في جافا

Answer 1

ويتعلق الأمر في الواقع إلى استخدام حق يقارن مع منتصف اختياره بشكل صحيح. على سبيل المثال (بدون تعريفات نوع متغير)،

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right)/2;
    if(a[mid] < val)
        return binsearch(a,val,mid+1,right);
    else
        return binsearch(a,val,left,mid);
}

وسوف تعطيك مؤشر أقصى اليسار العنصر الذي مباريات فال (حتى لو كان هو العنصر أقصى اليمين في المصفوفة). كنت لا تحتاج إلى التحقق صراحة الماضيين أو جولة يصل بدلا من استخدام بنيت في اقتطاع صحيح.

ولكن، إذا كنت ترغب في فهرس العنصر أقصى اليمين التي تساوي فال فأنت بحاجة إلى تغيير <مشغل ل> وينبغي إيلاء منتصف كتبها

mid = (left+right+1)/2;

وانها بهذه البساطة.

وتحرير: أكثر شيء واحد، وأنا نظرت إلى قانون بلدي التي تستخدم لهذا، وأدركت أن لديك لتغيير أيضا المكالمات إلى binsearch في نهاية المطاف على العنصر أقصى اليمين. أنا مجرد وظيفة رمز الكامل لهذا (والذي أرجو أن يكون ذلك في المقام الأول). وهنا بحث ثنائي للعثور على عنصر أقصى اليمين يساوي فال.

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right+1)/2;
    if(a[mid] > val)
        return binsearch(a,val,left,mid-1);
    else
        return binsearch(a,val,mid,right);
}

Answer 2

أبسط النهج هو استخدام نصف مفتوح النطاقات.هذه الطريقة العلوي نقاط خطوة واحدة بعد آخر صالحة عنصر في مجموعة, بالرغم من الأدنى نقاط مباشرة إلى البند الأول.ولكن أثناء البحث ، يمكنك التعامل مع مجموعة شاملة - على الخروج من النطاق الأعلى هو صالح "لا مباراة وجدت" نتيجة.

في بداية كل تكرار لديك...

lower <= target <= upper

"الهدف" يعني المؤشر التي سيتم العثور عليها وإعادتها.

يمكنك حساب متوسط باسم "(علوي + سفلي) / 2".لأن هذا باقتطاع ، منتصف يمكن أن يكون أبدا نفس العليا ، وهو أمر مهم.منذ "العلوي" قد تكون خارج حدود, نحن لا يمكن أبدا قانونا تقييم "مجموعة [العلوي]".

العثور على البند الأول أكبر من أو يساوي-الرئيسية...

if array[mid] >= k :  lower <= target <= mid
if array[mid] <  k :  mid+1 <= target <= upper

العثور على البند الأول أكبر من المفتاح...

if array[mid] >  k :  lower <= target <= mid
if array[mid] <= k :  mid+1 <= target <= upper

هذه subranges شاملة ، يجب على وجه التحديد تلبية لكن لا تتداخل.عنصر واحد التداخل في منتصف (خطأ سهل) النتائج في حلقات لانهائية ، والتي هي جزء من السبب في أننا نستخدم متوسط+1 واحد subrange.

لاحظ أن كل هذه التغييرات بين اثنين البحث هو المقارنة المشغل.

للعثور على آخر أقل أو تساوي ، والعثور على أول زيادة في طرح واحد من النتيجة.يمكنك الحصول على -1 إذا كانت جميع العناصر في الصفيف أكبر من المفتاح.

ملاحظة - يمكنك فقط اختبار مفتاح ضد منتصف في كل تكرار (هل تعلم أن الحدود العليا والسفلى هي صحيحة بالفعل) وأنت فقط واحد مشروطا الاختبار.

هل الخروج من حدود الاختيار والمساواة الاختيار (إذا كان هذا ما تحتاجه) خارج من حلقة.

int find_first_ge (int key)
{
  int lower = 0;
  int upper = array.length;

  while (upper > lower)
  {
    int mid = (lower + upper) / 2;

    if (array [mid] >= key)  //  for find_first_gt, use ">" here
    {
      upper = mid;
    }
    else
    {
      lower = mid + 1;
    }
  }

  return lower;
}

ملاحظة

التعديل لتصحيح بعض الأخطاء التي تركت هذا فقط لانهائية-loopy ما كان من المفترض أن إصلاح.

الخدعة هو التأكد من أن شطر subranges هي بالضبط حسب الحاجة بعد كل اختبار ، دائما واحد على الأقل أصغر من الأصلي النطاق الكامل - ومن خلال الثقة المفرطة و ذاكرة سيئة, هذا بالضبط ما تمكنت من الحصول على الخطأ.أعلاه هو العامل التعليمات البرمجية في بالسلاح استخدام المكتبة (البحث ضمن عقدة في multiway شجرة المكتبة) ، حتى لو كان خطأ عندي كبير مشاكل ;-)

ملاحظة

تحريرها مرة أخرى من أجل تحسين صياغة وتبسيط subrange حدود الوصف (وإذ يلاحظ أنه على الرغم من نطاقات نصف مفتوحة ، فهي تعامل على أنها شاملة).

Answer 3

وعندما الخاص بك الأدنى والحد الأعلى الخاص بك تقع ضمن واحدة من بعضها البعض، والتحقق من كليهما.

Answer 4

هل يمكن محاصرة في كل مرة.

و(6 + 7) /2.0 == 6.5

وجولة منه وعليك أن تأتي مع 7.

وأو هل يمكن ببساطة إضافة إلى منتصف الخاص بك.

ومنتصف = (6 + 7) / 2 + 1

وهناك طريقة أخرى يتغير نقطة البداية أو النهاية ل+1 أو -1 لالعودية التالية. هذا هو ما المادة ويكيبيديا على عروض الموضوع في بعض التطبيقات.

ودقيقة = منتصف + 1

أو

والحد الأقصى = منتصف 1

Answer 5

وبحث ثنائي هو صعب المعروف أن الحصول على حق تماما. هناك تحليل دقيق جدا حول مختلف المشاكل والقضايا الحافة، جنبا إلى جنب مع التنفيذ الصحيح، في <لأ href = "http://www.amazon.co.uk/Programming-Pearls-ACM-Press-Bentley/dp/ 0201657880 "يختلط =" noreferrer نوفولو "> اللؤلؤ البرمجة ، وهو الكتاب الذي كل مبرمج ربما ينبغي أن قرأت ما لا يقل عن مرة واحدة.