Tìm kiếm nhị phân (binary search), còn gọi là tìm kiếm logarithmic, là thuật toán tìm kiếm phần tử trong một mảng đã được sắp xếp. Thuật toán chia mảng thành hai nửa, nếu phần tử trung bằng giá trị cần tìm thì trả về, ngược lại đệ quy tìm trên nửa phù hợp cho đến khi tìm thấy.
Cơ chế hoạt động
Thuật toán so sánh phần tử giữa của mảng đã sắp xếp với giá trị cần tìm:
- Nếu bằng phần tử giữa → trả về chỉ số của phần tử.
- Nếu lớn hơn phần tử giữa → tìm kiếm trên mảng con bên phải (từ phần tử sau giữa đến cuối).
- Nếu nhỏ hơn phần tử giữa → tìm kiếm trên mảng con bên trái (từ đầu đến phần tử trước giữa).
Cú pháp
binary_search(start_address, end_address, element)
Tham số
start_address: địa chỉ phần tử đầu tiên của mảng.end_address: địa chỉ phần tử cuối cùng của mảng.element: giá trị cần tìm.
Giá trị trả về
Trả về true (1) nếu tìm thấy, ngược lại trả về false (0).
Ví dụ minh họa
#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 << "Cac phan tu cua mang:\n";
printArray(arr, sizeofarr);
cout << "\nDang sap xep mang...";
sort(arr, arr + sizeofarr);
cout << "\nMang da sap xep: ";
printArray(arr, sizeofarr);
cout << "\nPhan tu can tim la 4";
if (binary_search(arr, arr + sizeofarr, 4))
cout << "\nTim thay phan tu";
else
cout << "\nKhong tim thay phan tu";
return 0;
}
Kết quả
Cac phan tu cua mang: 1 5 9 7 3 2 0 4 Dang sap xep mang... Mang da sap xep: 0 1 2 3 4 5 7 9 Phan tu can tim la 4 Tim thay phan tu