البحث الثنائي (2) Binary Search

من طرف Ebisu الأربعاء يونيو 16, 2010 11:57 am

بسم الله
الرحمن الرحيم

بعد أن تعرفنا على خوارزم الـBinary

Search وطبقناه على مصفوفة ذات عناصر رقمية، نتعرف في هذا الدرس
على
المكتبة الجاهزة والتي توفرها الجافا كي نطبق الـBinary

Search على مصفوفة ذات عناصر حرفية strings..

جميع المكتبات التي سنستخدمها
هنا وفرتها الـJava Collections

Framework، وسنستخدم مكتبتين:

Collections.binarySearch:
والتي تأخذ list
كـ
argument أول لها، وتأخذ
Object كـ argument

ثاني. فتقوم بالبحث عن الـObject

داخل الـList

باستخدام تكنيك الـbinary search والذي
شرحناه في
الدرس الأول.

Collections.sort: والتي تأخذ
List كـ argument

وحيد لها، وتقوم بترتيبها أبجدياً.

ولكي نستطيع استخدام هذه
المكتبات، لابد لنا من أن نضع جميع العناصر الحرفية في
list (سواء اخترنا
ArrayList, LinkedList or Vector) وسنختار هنا الـArrayList.
ويوضح الـcode التالي كيفية تعريف هذا النوع
من الـlist
وكيفية تطبيق هذه المكتبات عليه، حيث أن الـbinarySearch
Method التي سنستخدمها ستعطينا في المخرجات:

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

قيمة سالبة إذا لم
يكن
المفتاح (العنصر الذي نبحث عنه) ينتمي إلى المصفوفة.

وإليك الشيفرة كاملة:

// Using algorithm binarySearch
import java.util.*;

public class BinarySearchTest {
private String colors[] = { "red", "white", "blue","black",
"yellow",
"purple", "tan", "pink" };
private ArrayList aList; // ArrayList
reference

public BinarySearchTest()
{
aList = new ArrayList( Arrays.asList( colors ) );
Collections.sort( aList ); // sort the
ArrayList
System.out.println( "Sorted ArrayList: " + aList );
}

public void printSearchResults()
{
printSearchResultsHelper( colors[ 3 ] ); //
first item
printSearchResultsHelper( colors[ 0 ] ); //
middle
item
printSearchResultsHelper( colors[ 7 ] ); //
last item
printSearchResultsHelper( "aardvark" ); //
below
lowest
printSearchResultsHelper( "goat" ); // doesnt
exist
printSearchResultsHelper( "zebra" ); // doesnt
exist
}

private void printSearchResultsHelper( String key )
{
int result = 0;

System.out.println( "nSearching for: " + key );
result = Collections.binarySearch( aList, key );
System.out.println( ( result >= 0 ? "Found at index " + result :
"Not Found
(" + result + ")" ) );
}

public static void main( String args[] )
{
new BinarySearchTest().printSearchResults();
}
}

والصورة التالية تريك شاشة
المخرجات:

البحث الثنائي (2) Binary Search Jbs

وبذلك نكون قد غطينا موضوع الـbinary

search في الجافا من جميع الجوانب ولله الحمد Smile