Thuật toán tìm kiếm nhị phân - Binary sort
Ý tưởng của thuật toán:
Phép tìm kiếm nhị phân được thực hiện trên dãy khoá có thứ tự (xét dãy tăng dần):
a[0]<=a[1]<=a[2]<=...<=a[n-1]. Giá trị cần tìm x.
Chia đôi dãy khoá cần tìm kiếm. So sánh khoá giữa dãy với x, có 3 trường hợp xãy ra:
- Giá trị khoá này bằng x, tìm kiếm thành công
- Giá trị khoá này lớn hơn x, thì ta tiến hành tìm x với nữa bên trái của khoá này
- Giá trị khoá này nhỏ hơn x, thì ta tiến hành tìm x với nữa bên phải của khoá này
Trường hợp tìm kiếm thất bại khi dãy khoá cần tìm không có phần tử nào.
Cài đặt Thuật toán [code Turbo C\C++]:
/*Thuật toán tìm kiếm nhị phân không đệ quy*/
int BinarySearch(int x, int a[],int n) // Tìm khoá x trong dãy a1,a2…,an
{
int left =0; //Left trỏ về chỉ số đầu dãy
int right =n-1; //right trỏ về vị trí cuối dãy
int mid; // mid trỏ vào giữa dãy
int found = 0; //dùng để xác tìm thành công hay không (0: không tìm thấy, 1: tìm thấy)
while (left <= right && found==0){
mid = (left + right) / 2;//mid ở giữa dãy
if (a[mid]== x) //trường hợp tìm thấy dừng thuật toán
found = 1;
else
if (a[mid]<x)
left = mid +1; //xác định lại đoạn tìm tiếp theo là bên phải
else
right = mid -1; //xác định lại đoạn tìm tiếp theo là bên trái
}
return found;
}
/*Thuật toán tìm kiếm nhị phân đệ quy*/
int BinSearch(int[] a, int gt, int dau, int cuoi)
{
int i, j;
i = dau; j = cuoi;
if (i > j)
{
return -1; // không tìm thấy
}
int giua = (i + j) / 2;
if (gt == a[giua])
{
return giua; // tìm thấy
}
else if (gt < a[giua])
{
j = giua - 1;
return BinSearch(a, gt, dau, j);
}
else
{
i = giua + 1;
return BinSearch(a, gt, i, cuoi);
}
}
// Đề nghị độc giả chuyể hàm cài trên sang đệ quy và viết đầy đủ chương trình để mo phỏng thuật toán.
--------------------------------------------
Xem thêm các thuật toán khác:
* Có thể bạn quan tâm:
- Những cuốn sách mà các bạn không thể bỏ qua khi còn trẻ
- Khoá học tin học văn phòng tốt nhất
Chúc các bạn thành công!