การค้นหาแบบทวิภาค (Binary Search) หรือที่รู้จักกันในชื่อ Logarithmic Search เป็นอัลกอริทึมค้นหาที่ใช้สำหรับค้นหาองค์ประกอบในอาร์เรย์ที่จัดเรียงแล้ว อัลกอริทึมนี้จะแบ่งอาร์เรย์ออกเป็นสองครึ่งอย่างต่อเนื่อง หากพบองค์ประกอบที่ตำแหน่งกลางจะคืนค่า มิฉะนั้นจะเรียกใช้งานแบ่งและตรวจสอบซ้ำจนกว่าจะพบองค์ประกอบนั้น
การทำงาน
อัลกอริทึมทำงานโดยการเปรียบเทียบองค์ประกอบตรงกลางของอาร์เรย์ที่จัดเรียงแล้ว กับองค์ประกอบที่ต้องการค้นหา
- ถ้าองค์ประกอบที่ค้นหา เท่ากับ องค์ประกอบกลาง ให้ คืนดัชนี (index) ขององค์ประกอบนั้น
- ถ้าองค์ประกอบที่ค้นหา มากกว่า องค์ประกอบกลาง ให้ ค้นหาในซับอาร์เรย์ด้านขวา คือ ซับอาร์เรย์จากองค์ประกอบถัดจากกลางจนถึงปลายอาร์เรย์
- ถ้าองค์ประกอบที่ค้นหา น้อยกว่า องค์ประกอบกลาง ให้ ค้นหาในซับอาร์เรย์ด้านซ้าย คือ ซับอาร์เรย์จากองค์ประกอบแรกจนถึงองค์ประกอบก่อนกลาง
รูปแบบการใช้งาน (Syntax)
binary_search(start_address, end_address, element)
พารามิเตอร์
- start_address คือ ที่อยู่ขององค์ประกอบแรกของอาร์เรย์
- end_address คือ ที่อยู่ขององค์ประกอบสุดท้ายของอาร์เรย์
- element คือ องค์ประกอบที่ต้องการค้นหาในอาร์เรย์
ค่าที่คืน
คืนค่า true (1) หากพบองค์ประกอบในอาร์เรย์ มิฉะนั้นคืนค่า false (0)
ตัวอย่างโค้ด
#include <algorithm>
#include <iostream>
using namespace std;
void printArray(int a[], int arraysize) {
for (int i = 0; i < arraysize; ++i)
cout << a[i] << " ";
}
int main() {
int arr[] = {1, 5, 9, 7, 3, 2, 0, 4};
int sizeofarr = sizeof(arr) / sizeof(arr[0]);
cout << "The Element of array are :\n";
printArray(arr, sizeofarr);
cout << "\nSorting Elements of array.";
sort(arr, arr + sizeofarr);
cout << "\nSorted array is : ";
printArray(arr, sizeofarr);
cout << "\nElement to be searched is 4";
if (binary_search(arr, arr + sizeofarr, 4))
cout << "\nElement found ";
else
cout << "\nElement not found";
}
ผลลัพธ์
The Element of array are : 1 5 9 7 3 2 0 4 Sorting Elements of array. Sorted array is : 0 1 2 3 4 5 7 9 Element to be searched is 4 Element found
