القفز على البحث
يحب البحث الثنائي Jump Search عبارة عن خوارزمية بحث عن المصفوفات المصنفة. الفكرة الأساسية هي التحقق من عدد أقل من العناصر (من البحث الخطي ) من خلال القفز للأمام بخطوات ثابتة أو تخطي بعض العناصر بدلاً من البحث في جميع العناصر.
على سبيل المثال، لنفترض أن لدينا مصفوفة arr[] بالحجم n وكتلة (سيتم القفز عليها) بالحجم m. ثم نبحث في الفهارس arr[0] arr[m] arr[2m].....arr[km] وهكذا. بمجرد أن نجد الفاصل الزمني (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
لنفكر في المصفوفة التالية: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). طول المصفوفة هو 16. سيجد بحث Jump القيمة 55 مع الخطوات التالية على افتراض أن حجم الكتلة المراد القفز إليها هو 4.
الخطوة 1: الانتقال من الفهرس 0 إلى الفهرس 4؛
الخطوة 2: الانتقال من الفهرس 4 إلى الفهرس 8؛
الخطوة 3: الانتقال من الفهرس 8 إلى الفهرس 12؛
الخطوة 4: بما أن العنصر الموجود في الفهرس 12 أكبر من 55، فسنعود خطوة للوراء للوصول إلى الفهرس 8.
الخطوة 5: قم بإجراء بحث خطي من الفهرس 8 للحصول على العنصر 55.
الأداء بالمقارنة مع البحث الخطي والثنائي:
إذا قارناه بالبحث الخطي والثنائي فظهر أنه أفضل من البحث الخطي ولكن ليس أفضل من البحث الثنائي.
الترتيب المتزايد للأداء هو:
البحث الخطي < jump search < binary search
ما هو حجم الكتلة الأمثل الذي يجب تخطيه؟
في أسوأ الحالات، يتعين علينا إجراء قفزات n/m وإذا كانت آخر قيمة تم التحقق منها أكبر من العنصر المطلوب البحث عنه، فإننا نقوم بإجراء مقارنات m-1 أكثر للبحث الخطي. وبالتالي فإن إجمالي عدد المقارنات في أسوأ الحالات سيكون ((n/m) + m-1). قيمة الدالة ((n/m) + m-1) ستكون الحد الأدنى عندما تكون m = √n. وبالتالي فإن أفضل حجم للخطوة هو m = √ ن.
خطوات الخوارزمية
- Jump Search عبارة عن خوارزمية للعثور على قيمة محددة في مصفوفة مرتبة من خلال الانتقال خلال خطوات معينة في المصفوفة.
- يتم تحديد الخطوات بواسطة sqrt لطول المصفوفة.
- فيما يلي خوارزمية خطوة بخطوة للبحث السريع:
- حدد حجم الخطوة m عن طريق أخذ sqrt لطول المصفوفة n.
- ابدأ من العنصر الأول في المصفوفة، ثم انتقل إلى خطوات m حتى تصبح القيمة عند هذا الموضع أكبر من القيمة المستهدفة.
بمجرد العثور على قيمة أكبر من الهدف، قم بإجراء بحث خطي بدءًا من الخطوة السابقة حتى يتم العثور على الهدف أو يكون من الواضح أن الهدف غير موجود في المصفوفة.
إذا تم العثور على الهدف قم بإرجاع فهرسه. إذا لم يتم إرجاع -1 للإشارة إلى أنه لم يتم العثور على الهدف في المصفوفة.
مثال 1 :
C++ // C++ program to implement Jump Search #include using namespace std ; int jumpSearch ( int arr [] int x int n ) { // Finding block size to be jumped int step = sqrt ( n ); // Finding the block where element is // present (if it is present) int prev = 0 ; while ( arr [ min ( step n ) -1 ] < x ) { prev = step ; step += sqrt ( n ); if ( prev >= n ) return -1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == min ( step n )) return -1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return -1 ; } // Driver program to test function int main () { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x n ); // Print the index where 'x' is located cout < < ' n Number ' < < x < < ' is at index ' < < index ; return 0 ; } // Contributed by nuclode
C #include #include int min ( int a int b ){ if ( b > a ) return a ; else return b ; } int jumpsearch ( int arr [] int x int n ) { // Finding block size to be jumped int step = sqrt ( n ); // Finding the block where element is // present (if it is present) int prev = 0 ; while ( arr [ min ( step n ) -1 ] < x ) { prev = step ; step += sqrt ( n ); if ( prev >= n ) return -1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == min ( step n )) return -1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return -1 ; } int main () { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int index = jumpsearch ( arr x n ); if ( index >= 0 ) printf ( 'Number is at %d index' index ); else printf ( 'Number is not exist in the array' ); return 0 ; } // This code is contributed by Susobhan Akhuli
Java // Java program to implement Jump Search. public class JumpSearch { public static int jumpSearch ( int [] arr int x ) { int n = arr . length ; // Finding block size to be jumped int step = ( int ) Math . floor ( Math . sqrt ( n )); // Finding the block where element is // present (if it is present) int prev = 0 ; for ( int minStep = Math . min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . min ( step n ) - 1 ) { prev = step ; step += ( int ) Math . floor ( Math . sqrt ( n )); if ( prev >= n ) return - 1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == Math . min ( step n )) return - 1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return - 1 ; } // Driver program to test function public static void main ( String [ ] args ) { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x ); // Print the index where 'x' is located System . out . println ( 'nNumber ' + x + ' is at index ' + index ); } }
Python # Python3 code to implement Jump Search import math def jumpSearch ( arr x n ): # Finding block size to be jumped step = math . sqrt ( n ) # Finding the block where element is # present (if it is present) prev = 0 while arr [ int ( min ( step n ) - 1 )] < x : prev = step step += math . sqrt ( n ) if prev >= n : return - 1 # Doing a linear search for x in # block beginning with prev. while arr [ int ( prev )] < x : prev += 1 # If we reached next block or end # of array element is not present. if prev == min ( step n ): return - 1 # If element is found if arr [ int ( prev )] == x : return prev return - 1 # Driver code to test function arr = [ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ] x = 55 n = len ( arr ) # Find the index of 'x' using Jump Search index = jumpSearch ( arr x n ) # Print the index where 'x' is located print ( 'Number' x 'is at index' ' %.0f ' % index ) # This code is contributed by 'Sharad_Bhardwaj'.
C# // C# program to implement Jump Search. using System ; public class JumpSearch { public static int jumpSearch ( int [] arr int x ) { int n = arr . Length ; // Finding block size to be jumped int step = ( int ) Math . Sqrt ( n ); // Finding the block where the element is // present (if it is present) int prev = 0 ; for ( int minStep = Math . Min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . Min ( step n ) - 1 ) { prev = step ; step += ( int ) Math . Sqrt ( n ); if ( prev >= n ) return - 1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == Math . Min ( step n )) return - 1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return - 1 ; } // Driver program to test function public static void Main () { int [] arr = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x ); // Print the index where 'x' is located Console . Write ( 'Number ' + x + ' is at index ' + index ); } }
JavaScript < script > // Javascript program to implement Jump Search function jumpSearch ( arr x n ) { // Finding block size to be jumped let step = Math . sqrt ( n ); // Finding the block where element is // present (if it is present) let prev = 0 ; for ( int minStep = Math . Min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . Min ( step n ) - 1 ) { prev = step ; step += Math . sqrt ( n ); if ( prev >= n ) return - 1 ; } // Doing a linear search for x in block // beginning with prev. while ( arr [ prev ] < x ) { prev ++ ; // If we reached next block or end of // array element is not present. if ( prev == Math . min ( step n )) return - 1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return - 1 ; } // Driver program to test function let arr = [ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ]; let x = 55 ; let n = arr . length ; // Find the index of 'x' using Jump Search let index = jumpSearch ( arr x n ); // Print the index where 'x' is located document . write ( `Number ${ x } is at index ${ index } ` ); // This code is contributed by _saurabh_jaiswal < /script>
PHP // PHP program to implement Jump Search function jumpSearch ( $arr $x $n ) { // Finding block size to be jumped $step = sqrt ( $n ); // Finding the block where element is // present (if it is present) $prev = 0 ; while ( $arr [ min ( $step $n ) - 1 ] < $x ) { $prev = $step ; $step += sqrt ( $n ); if ( $prev >= $n ) return - 1 ; } // Doing a linear search for x in block // beginning with prev. while ( $arr [ $prev ] < $x ) { $prev ++ ; // If we reached next block or end of // array element is not present. if ( $prev == min ( $step $n )) return - 1 ; } // If element is found if ( $arr [ $prev ] == $x ) return $prev ; return - 1 ; } // Driver program to test function $arr = array ( 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ); $x = 55 ; $n = sizeof ( $arr ) / sizeof ( $arr [ 0 ]); // Find the index of '$x' using Jump Search $index = jumpSearch ( $arr $x $n ); // Print the index where '$x' is located echo 'Number ' . $x . ' is at index ' . $index ; return 0 ; ?>
الإخراج:
Number 55 is at index 10
تعقيد الوقت : O(?n)
المساحة المساعدة : O(1)مزايا البحث السريع:
- أفضل من البحث الخطي عن المصفوفات حيث يتم توزيع العناصر بشكل موحد.
- يتميز البحث السريع بتعقيد زمني أقل مقارنة بالبحث الخطي للمصفوفات الكبيرة.
- يتناسب عدد الخطوات المتخذة في البحث السريع مع الجذر التربيعي لحجم المصفوفة مما يجعلها أكثر كفاءة للمصفوفات الكبيرة.
- إنه أسهل في التنفيذ مقارنة بخوارزميات البحث الأخرى مثل البحث الثنائي أو البحث الثلاثي.
- يعمل البحث السريع بشكل جيد مع المصفوفات حيث تكون العناصر مرتبة وموزعة بشكل موحد حيث يمكنها الانتقال إلى موضع أقرب في المصفوفة مع كل تكرار.
نقاط مهمة:
- يعمل فقط مع المصفوفات التي تم فرزها.
- الحجم الأمثل للكتلة المراد القفز عليها هو (؟ ن). وهذا يجعل التعقيد الزمني لـ Jump Search O(?n).
- يقع التعقيد الزمني للبحث السريع بين البحث الخطي ((O(n)) والبحث الثنائي (O(Log n)).
- يعد البحث الثنائي أفضل من Jump Search ولكن يتميز Jump Search بأنه يمكننا الرجوع للخلف مرة واحدة فقط (قد يتطلب البحث الثنائي ما يصل إلى O(Log n) من القفزات، مع الأخذ في الاعتبار الموقف الذي يكون فيه العنصر المطلوب البحث فيه هو أصغر عنصر أو أكبر من الأصغر). لذلك، في النظام الذي يكون فيه البحث الثنائي مكلفًا، نستخدم Jump Search.
مراجع:
https://en.wikipedia.org/wiki/Jump_search
إذا كنت تحب GeeksforGeeks وترغب في المساهمة، يمكنك أيضًا كتابة مقال باستخدام write.geeksforgeeks.org أو أرسل مقالتك بالبريد إلى [email protected]. راجع مقالتك التي تظهر على صفحة GeeksforGeeks الرئيسية وساعد Geeks الآخرين. يرجى كتابة التعليقات إذا وجدت أي شيء غير صحيح أو كنت ترغب في مشاركة المزيد من المعلومات حول الموضوع الذي تمت مناقشته أعلاه.
