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

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

بعد أن تعرفنا على خوارزم الـ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();
}
}