امتداد لخوارزمية البحث الثنائي للعثور على الفهرس الأول والأخير لقيمة المفتاح المطلوب البحث عنها في مصفوفة

Question

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

وأيضًا، ما هو الحد الأقصى والأدنى لعدد المقارنات التي قد نحتاجها للعثور على الفهارس؟

Answer 1

إذا كنت ذكيًا بعض الشيء، فيمكنك تحديد وظيفتين مختلفتين للبحث الثنائي.سيقوم أحدهما بإرجاع فهرس أول ظهور للقيمة التي تم البحث عنها وسيقوم الآخر بإرجاع آخر ظهور للقيمة التي تم البحث عنها.من خلال معرفتك بالبحث الثنائي، يجب أن تكون قادرًا على تحديد الحد الأقصى والحد الأدنى لعدد المقارنات.

يجب أن يكون استخدام بحثين ثنائيين هو أسرع طريقة في المتوسط ​​في رأيي.على سبيل المثال، إذا كنت تستخدم بحثًا ثنائيًا واحدًا فقط للعثور على العنصر الأول ثم تبحث خطيًا بعد ذلك، فإن أسوأ الحالات ستكون إذا كانت الوظيفة بأكملها هي نفس القيمة.بالنسبة لمصفوفة بطول 10000، فإن هذا من شأنه أن يعطي 10013 مقارنة في أسوأ الحالات بينما استخدام بحثين ثنائيين سيعطي 28 مقارنة في أسوأ الحالات لنفس المصفوفة.بالطبع، باستخدام نفس حجم المصفوفة، فإن أفضل حالة لطريقة البحث الثنائي/الخطي هي 14 مقارنة بينما أفضل حالة لطريقتي بحث ثنائي هي 26 مقارنة.

** تحديث

حسنًا، إليك بحث ثنائي للعثور على أول ظهور لعنصر في مصفوفة.سأعطيك وظيفة متكررة (يمكنك بالطبع جعلها متكررة وتحسينها بطرق أخرى).هذا يبحث عن int val في المصفوفة a من ints.وأيضًا، لم أكن حريصًا بشأن العثور على نقطة المنتصف (إذا كانت المصفوفة كبيرة بالفعل، فقد تكون هناك مشكلات).

int bs1(int a[], int val, int left, int right)
{
    if(right == left) return left;
    int mid = (right+left)/2;

    if(val > a[mid]) return bs1(a, val, mid+1, right);
    else return bs1(a, val, left, mid);
}

ومع ذلك، يجب عليك التحقق بعد إرجاع الفهرس الذي يشير فعليًا إلى القيمة الصحيحة لأنه إذا لم يكن val موجودًا في المصفوفة، فسيتوافق الفهرس الذي تم إرجاعه مع العنصر التالي الأكبر من val.

ستؤدي بعض التغييرات الطفيفة إلى إنشاء دالة تعثر على العنصر الأخير.مفاتيح القيام بذلك هي استخدام المقارنات بشكل صحيح وتذكر أن تقسيم الأعداد الصحيحة يتم اقتطاعه دائمًا.

Answer 2

ل C ++، يمكنك البحث عن std::equal_range() ومتطلبات التعقيد لها. طالما كنت مهتما في الخوارزمية الأساسية، يجب تطبيق القواعد العامة نفسها بغض النظر عن استخدام اللغة للتنفيذ.

Answer 3

من السهل إلى حد ما القيام به دون كتابة خوارزمية البحث الثنائية الخاصة بك، من خلال استدعاء خوارزمية قياسية مرارا وتكرارا.

// some curly-bracket language:

// int BinarySearch(sortedList, searchIndex, searchLength, valueToFind)
// returns the zero-based index of the item in the list, or a negative value
// if the item is not found

int inner = BinarySearch(list, 0, listSize, value);
if(inner < 0){
    // handle case where value is not found in list
}

int bottom = inner, top = inner;
while(true){
    int i = BinarySearch(list, 0, bottom, value);
    if(i < 0)
        break;
    bottom = i;
}
while(true){
    int i = BinarySearch(list, top + 1, listSize - top - 1, value);
    if(i < 0)
        break;
    top = i;
}

// bottom and top now hold the bounds of all instances of value in list

هذا قريب جدا من نفس الكفاءة التي تحصل عليها مع خوارزمية مخصصة، إلا أن لديك المزيد من الدالة استدعاء النفقات العامة.

بالنسبة لعدد المقارنات، يجب أن أفكر بضيق بعض الشيء، لكنني أعتقد أنه سجل 2 * فقط₂ن، حيث n هو عدد العناصر في القائمة.

---

تعديل

باه! ليس 2 * سجل₂ن، لأنه على عكس ما يمكنك القيام به مع خوارزمية مخصصة، فإنه لا يستبعد أجزاء تدريجيا من القائمة. يظهر¹ أن الحد الأقصى لعدد المقارنة هو (السجل₂N - 0.5) * سجل₂N. لا يزال هذا فقط 885 مقارنات لقائمة مع 2³⁰ العناصر (390 مقارنات لشخصين²⁰ ن، و 95 لمدة 2¹⁰ ن)، ولكن يمكننا أن نفعل أفضل من ذلك.

// int Compare(a, b)
// returns 0 if a and b are equal,
//         a negative value if a < b, or
//         a positive value if a > b

int start = 0, end = listSize, inner;

while(true){
    if(end == start){
        // handle case where value is not found in list
    }
    inner = (start + end) / 2;
    int cmp = Compare(list[inner], value);
    if(cmp == 0)
        break;
    if(cmp < 0)
        start = inner + 1;
    else end = inner;
}

int top = inner, bottom = inner;

while(true){
    if(start >= bottom)
        break;
    inner = (start + bottom) / 2;
    int cmp = Compare(list[inner], value);
    if(cmp == 0)
        bottom = inner;
    else start = inner + 1;
}

while(true){
    if(end - 1 <= top)
        break;
    inner = (top + 1 + end) / 2;
    int cmp = Compare(list[inner], value);
    if(cmp == 0)
        top = inner;
    else end = inner;
}

هذا سوف يفعل على الأكثر 2 * سجل₂مقارنات ن. 2.³⁰ سوف تتطلب العناصر على الأكثر 60 مقارنات، 2²⁰ سوف تتطلب العناصر على معظم مقارنات 40، إلخ.

---

_{¹ لقد قررت هذا تجريبيا. أنا لست ذكيا تماما بما يكفي لمعرفة ذلك رياضيا.}

Answer 4

يمكنك العثور على المناقشة حول هذا في بنتلي لآلئ البرمجة و knuth's vol.3: الفرز والبحث.

هنا هو تطبيق واحد في C ++: http://the-algo-blog.blogspot.com/2012/binary-search-find-last-first.html.

Answer 5

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

إخلاء المسئولية: غير اختبارها؛ من المفترض أن تظهر الفكرة وعدم استخدامها مباشرة كصن رمز الإنتاج

int org = binarySearch(array,value) //do the binary search and find on element
int min = org-delta; //delta is some constant based on how many elemts are to be expected
int max = org;
min = min < 0 ? 0 : min;
int search= min;
bool latestWasHit = false;
while(search > 0)
{
  if(search+1 == max)
     return max;
  if(array[search] != value)
  {
     min = search;
     search = search + (max-search)/2
  }
  else
  {
     max = search;
     search = (search-min)/2;
  } 
}

ثم عكس الحد العلوي. ومع ذلك، سيتطلب الأمر الكثير من العناصر قبل أن يكون هذا أسرع من البحث الخطي البسيط.

Answer 6

أتصور أن الخوارزمية العادية سيكون لها شيء مثل هذا في ذلك:

if(value == test) return;
if(value < test) min = i;
if(value > test) max = i;

بمجرد أن تكون قد استخدمت هذا للعثور على إحدى القيم، قم بإجراء عمليات تفتيش ثنائية معدلة أكثر قليلا باستخدام MIN و MAX لديك حاليا للعثور على النصائح.

للعثور على أعلى معظم استبدال ما سبق مع:

if(value <= test) min = i;
if(value > test) max = i;

بالنسبة إلى أسفل معظم استبدال مع:

if(value >= test) max = i;
if(value < test) min = i;

ملاحظة لا توجد عودة مبكرة باستخدام هذه الطريقة، فإنك تستمر فقط في الذهاب حتى دقيقة و Max هي مثل واحد أو شيء منفصل، أفترض أنك يمكن أن تضيف واحدة مع شيك آخر

if(value == test and arr[i-1] != test) return;

إلخ.

Answer 7

لقد قمت بإنشاء طريقتين بحثين ثنائية للعودة إلى الحوادث الأولى والأخيرة على التوالي.

public static void main(String[] args) {
    int a[] ={1,2,2,2,2,2,5,5,6,8,9,10};

    System.out.println(5+" first = "+first(a, 5, 0, a.length-1));
    System.out.println(5+" last = "+right(a, 5, 0, a.length-1));

    System.out.println(1+" first = "+first(a, 1, 0, a.length-1));
    System.out.println(1+" last = "+right(a, 1, 0, a.length-1));

    System.out.println(2+" first = "+first(a, 2, 0, a.length-1));
    System.out.println(2+" last = "+right(a, 2, 0, a.length-1));

    System.out.println(10+" first = "+first(a, 10, 0, a.length-1));
    System.out.println(10+" last = "+right(a, 10, 0, a.length-1));

    System.out.println(8+" first = "+first(a, 8, 0, a.length-1));
    System.out.println(8+" last = "+right(a, 8, 0, a.length-1));

    System.out.println(11+" first = "+first(a, 11, 0, a.length-1));
    System.out.println(11+" last = "+right(a, 11, 0, a.length-1));


}

private static int first(int [] a, int x, int l, int h){
    if(l>h){
        return -1;
    }
    int mid = (h-l)/2+l;
    if(a[mid] == x && (mid==0 || a[mid-1] != x) ){
        return mid;
    }else if(a[mid] == x){
        return first(a, x, l, mid-1);
    }else if(a[mid]>x){
        return first(a, x, l, mid-1);
    }else{
        return first(a, x, mid+1, h);
    }
}


private static int right(int [] a, int x, int l, int h){
    if(l>h){
        return -1;
    }
    int mid = (h-l)/2+l;
    if(a[mid] == x && (mid==a.length-1 || a[mid+1] != x) ){
        return mid;
    }else if(a[mid] == x){
        return right(a, x, mid+1, h);
    }else if(a[mid]>x){
        return right(a, x, l, mid-1);
    }else{
        return right(a, x, mid+1, h);
    }
}

Output:
    1 first = 0
    1 last = 0
    2 first = 1
    2 last = 5
    10 first = 11
    10 last = 11
    8 first = 9
    8 last = 9
    11 first = -1
    11 last = -1