Chương 6: SẮP XẾP VÀ TÌM KIẾM (SORTING AND SEARCHING)
6.9.2. Tìm kiếm nhị phân (Binary Searching)
Tìm kiếm nhị phân là phương pháp tìm kiếm phổ biến được thực hiện trên một dãy đã được sắp thứ tự. Nội dung của giải thuật được thực hiện như sau: lấy khóa cần tìm kiếm X so sánh với nội dung của khóa của phần tử ở giữa, vị trí của phần tử ở giữa là mid = (low + hight )/ 2, trong đó cận dưới low =0, cận trên hight = n-1. Vì dãy đã được sắp xếp nên nếu nội dung của khóa tại vị trí giữa lớn hơn X thì phần tử cần tìm thuộc khoảng [mid+1, hight], nếu nội dung của khóa tại vị trí giữa nhỏ hơn X thì phần tử cần tìm thuộc khoảng [low, mid- 1], nếu nội dung của khóa tại vị trí giữa trùng với X thì đó chính là phần tử cần tìm. Ở bước tiếp theo, nếu nội dung của khóa tại vị trí giữa lớn hơn X thì ta dịch chuyển cận dưới low lên vị trí mid+ 1, nếu nội dung của khóa tại vị trí giữa nhỏ hơn X thì ta dịch chuyển cận trên về vị trí mid- 1. Quá trình được lặp lại cho tới khi gặp khóa có nội dung trùng với X hoặc cận dưới vượt quá cận trên hay X không thuộc dãy. Thuật toán tìm kiếm nhị phân được minh họa như sau:
int Binary_Search( int *A, int X, int n){
int mid, low=0, hight = n-1;
while ( low<=hight ){ // lặp nếu cận dưới vẫn nhỏ hơn cận trên mid = (low + hight) /2; // xác định vị trí phần tử ở giữa if (X > A[mid] ) low = mid +1; // X thuộc [mid+1, hight]
else if (X < A[mid] ) hight = mid- 1; // X thuộc [low, mid-1]
else return(mid);
}
return(-1); // X không thuộc dãy }
Chương trình cụ thể được cài đặt như sau:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>
#include <dos.h>
int Binary_Search( int *, int, int);
void Bubble(int *, int);
void Init(int *, int);
int Binary_Search( int *A, int X, int n) { int mid, low = 0, hight = n-1;
while (low<=hight){
mid = (low +hight)/2;
if (X >A[mid] ) low = mid +1;
else if (X<A[mid] ) hight = mid -1;
else return (mid);
}
return(-1);
}
void Init(int *A, int n){
int i;
printf("\n Tao lap day so:");
for (i=0; i<n;i++){
A[i]=random(1000);
printf("%5d",A[i]);
}
delay(1000);
}
void Bubble(int *A, int n){
register i,j,temp;
for (i=1; i<n; i++){
for (j=n-1; j>=i;j--){
if (A[j-1]>A[j]){
temp=A[j-1];
A[j-1]=A[j];
A[j]=temp;
}
}
printf("\n Ket qua lan:%d", i);
In(A,n);
} }
void In(int *A, int n){
register int i;
for(i=0;i<n;i++)
printf("%5d",A[i]);
delay(1000);
}
void main(void){
int *A,n, X, k;clrscr();
printf("\n Nhap n="); scanf("%d",&n);
printf(“\n Số cần tìm X=”); scanf(“%d”,&X);
A=(int *) malloc(n*sizeof(int));
Init(A,n);Bubble(A,n); k= Binary_Search(A, X, n);
if ( k>0)
printf (“\n %d ở vị trí số %d”, X, k);
else
printf(“\n %d không thuộc dãy”);
getch();
free(A);
}
NHỮNG NỘI DUNG CẦN GHI NHỚ
9 Hiểu được ý nghĩa vai trò của bài toán sắp xếp và tìm kiếm trong tin học.
9 Cài đặt nhuần nhuyễn các giải thuật sắp xếp và tìm kiếm trên các cấu trúc dữ liệu khác nhau.
9 Giải quyết các bài tập thực hành kèm theo làm thăng tiến kỹ năng giải quyết bài toán sắp xếp & tìm kiếm.
BÀI TẬP CHƯƠNG 6
Bài 1. Cài đặt chương trình theo thuật toán Quick Sort không dùng phương pháp đệ qui mà dùng cấu trúc stack.
Bài 2. Tìm hiểu về giải thuật Shell-Sort là phương pháp cải tiến của Insertion Sort.
Bài 3. Cài đặt lại giải thuật Bubble Sort sao cho các node nhỏ được đẩy dần về phía trước.
Bài 4. Một Ternary Heap là cây tam phân gần đầy được cài đặt bằng mảng một chiều, mỗi node có ba node con. Nội dung của node cha bao giờ cũng lớn hơn hoặc bằng nội dung của node con, các node được đánh số từ 0 đến n-1, node i có 3 con là 3i+1, 3i+2, 3i+3. Hãy cài đặt giải thuật Ternary Heap.
Bài 5. Cài đặt giải thuật Bubble Sort trên file.
Bài 6. Cài đặt giải thuật Insertion Sort trên file.
Bài 7. Cài đặt giải thuật Quick Sort trên file.
Bài 8. Cài đặt các giải thuật sắp xếp theo nhiều khoá khác nhau.
Bài 9. Nghiên cứu và cài đặt thuật toán tìm kiếm tam phân.
Bài 10. Nghiên cứu và cài đặt thuật toán sắp xếp kiểu hoà nhập thực hiện trên file.
Bài 11. Viết chương trình chuyển đổi một file dữ liệu được tổ chức theo khuôn dạng *.DBF thành file kiểu text. Ngược lại, chuyển đổi file dữ liệu kiểu text thành một file dữ liệu theo khuôn dạng DBF.
Bài 12. Tìm hiểu cách sắp xếp và tìm kiếm theo kiểu index của các hệ quản trị cơ sở dữ liệu như foxprol hoặc access.
TÀI LIỆU THAM KHẢO
[1] Lê Hữu Lập - Nguyễn Duy Phương. Giáo trình Kỹ thuật lập trình. NXB Bưu Điện, 2002.
[2] Đỗ Xuân Lôi. Cấu trúc dữ liệu và giải thuật. NXB Khoa Học Kỹ Thuật, 2000.
[3] Đặng Huy Ruận. Lý thuyết đồ thị. NXB Khoa Học Kỹ Thuật, 2003
[4] William Ford, William Topp. Data Structures with C++. Prentice Hall, 1996.
[5] Mark Allen Weiss. Data Structures and Algorithm Analysis In C. Prentice Hall, 1996.
[6] Phan Đăng Cầu. Cấu trúc dữ liệu và Giải thuật (Tài liệu giảng dạy–Học Viện Công nghệ BCVT), 2003.