طي طريقة التراجع نصف :
في جدول مرتبة ، قارن قيمة البيانات المراد البحث فيها مع قيمة العنصر الوسيط لنطاق البحث ، وستكون هناك ثلاث حالات:
1) إذا كانت قيمة البيانات الواجب العثور عليها تساوي تمامًا قيمة العنصر الوسيط ، فأعد فهرس قيمة العنصر المتوسط.
2) إذا كانت قيمة البيانات المراد البحث فيها أصغر من قيمة العنصر الوسيط ، فاستخدم النصف الأول من نطاق البحث بأكمله كنطاق بحث جديد ، وتنفيذ 1) حتى يتم العثور على قيمة متساوية.
3) إذا كانت قيمة البيانات المراد البحث فيها أكبر من قيمة العنصر الوسيط ، فاستخدم النصف الثاني من نطاق البحث بأكمله كمدى بحث جديد ، وتنفيذ 1) حتى يتم العثور على القيمة المتساوية.
4) إذا كان لا يمكن العثور على نفس القيمة في النهاية ، فسيتم إرجاع رسالة الخطأ.
وفقًا للشجرة الثنائية ، فإن القيمة الوسطى هي جذر الشجرة الثنائية ، والنصف الأول هو الشجرة الفرعية اليسرى ، والنصف الثاني هو الشجرة الفرعية اليمنى. عدد عمليات البحث عن طريقة البحث نصف المنزلية هو بالضبط عدد الطبقات التي توجد فيها القيمة. تحت احتمال متساوٍ تقريبًا
log2 (n+1) -1
نسخة الكود كما يلي:
// البيانات هي المصفوفة التي سيتم البحث فيها ، x هي قيمة البيانات التي سيتم البحث عنها ، والاستخلاص هي بداية نطاق البحث ، والأخير هو نهاية نطاق البحث
// طريقة غير متكررة
int bisearch (int data [] ، const int x ، int beg ، int last)
{
int mid ؛ // الوضع الأوسط
إذا (التسول> الماضي)
{
العودة -1 ؛
}
بينما (BEG <= Last)
{
mid = (beg + last) / 2 ؛
إذا (x == بيانات [منتصف])
{
العودة في منتصف
}
آخر إذا (البيانات [Mid] <x)
{
BEG = MID + 1 ؛
}
آخر إذا (البيانات [MID]> X)
{
الأخير = منتصف - 1 ؛
}
}
العودة -1 ؛
}
// طريقة العودية
int iterbisearch (int data [] ، const int x ، int beg ، int last)
{
int mid = -1 ؛
mid = (beg + last) / 2 ؛
إذا (x == بيانات [منتصف])
{
العودة في منتصف
}
آخر إذا (x <data [mid])
{
إرجاع iterbisearch (البيانات ، x ، beg ، mid - 1) ؛
}
آخر إذا (x> البيانات [mid])
{
إرجاع iterbisearch (البيانات ، x ، mid + 1 ، last) ؛
}
العودة -1 ؛
}
// الوظيفة الرئيسية
int _tmain (int argc ، _tchar* argv [])
{
int data1 [60] = {0} ؛
int no2search = 45 ؛
cout << "الصفيف هو:" << endl ؛
int siz = sizeof (data1)/sizeof (int) ؛
لـ (int i = 0 ؛ i <siz ؛ i ++)
{
Data1 [i] = i ؛
cout << data1 [i] << "" ؛
}
cout << endl ؛
int index = -1 ؛
// index = bisearch (data1 ، no2search ، 0 ، siz) ؛
index = iterbisearch (data1 ، no2search ، 0 ، siz) ؛
cout << "فهرس" << no2search << "هو" << index << endl ؛
getchar () ؛
العودة 0 ؛
}
نسخة الكود كما يلي:
/**
* نصف للعثور على موضع الأحرف في المصفوفة (القائمة المطلوبة)
* @param array صفيف الاسترداد
* @param x أحرف يمكن العثور عليها
* returns موضع الحرف في الصفيف ، لم يتم العثور على نتائج وإرجاع -1
*/
وظيفة BinarySearch (Array ، X) {
var lowpoint = 1 ؛
var higpoint = array.length ؛
var returnvalue = -1 ؛
var midpoint ؛
وجدت var = false ؛
بينما ((lowpoint <= higpoint) && (! وجدت)) {
midpoint = math.ceil ((lowpoint+higpoint)/2) ؛
//console.log(lowpoint+"==="+midpoint+"==="+higpoint) ؛
if (x> array [midpoint-1]) {
lowpoint = midpoint+1 ؛
}
آخر إذا (x <array [midpoint-1]) {
higpoint = midpoint-1 ؛
}
آخر إذا (x = صفيف [midpoint-1]) {
وجدت = صواب ؛
}
}
إذا (تم العثور عليه) {
ReturnValue = نقطة الوسط ؛
}
إرجاع القيمة ؛
}
/*var array2 = [1،2،3،4،5،6،7،8،9،100،109] ؛*/
var array2 = ['a' ، 'b' ، 'c' ، 'd' ، 'e' ، 'f' ، 'g'] ؛
console.log (BinarySearch (Array2 ، 'c')) ؛