Chương 2.1. Giải thuật tìm kiếm
Trần Minh Thái
Email: [email protected]
Website: www.minhthai.edu.vn
1
Mục tiêu

Xác định được vai trò của tìm kiếm và sắp xếp trong hệ thống thông tin

Nắm vững và minh họa được giải thuật tìm kiếm tuyến tính và tìm kiếm nhị phân
trên mảng một chiều

Cài đặt được giải thuật tìm kiếm bằng ngôn ngữ C/C++
2
Suy nghĩ
3
Tại sao hầu hết phần mềm phải có chức năng m kiếm và sắp xếp, mối quan
hệ giữa m kiếm và sắp xếp?
?
Nhu cầu tìm kiếm và sắp xếp

Tìm kiếm: Có trong hầu hết trong các hệ thống thông tin

Muốn tìm kiếm nhanh và hiệu quả  dữ liệu có thứ tự  sắp xếp
4
Các giải thuật tìm kiếm

Có 2 giải thuật thường được áp dụng: Tìm tuyến tính và tìm nhị phân.

Đặc tả:


6
Tìm kiếm tuyến tính

Minh họa tìm x =10

Minh họa tìm x =25
7
Chưa hết mảng
7 5 12 41 10 32 13 9 15 3
1 2 3 4 5 6 7 8 9 10
7 5 12 41 10 32 13 9 15 3
1 2 3 4 5 6 7 8 9 10
10
10
25
Chưa hết
mảng
Đã m thấy tại
vị trí 5
Đã hết mảng
Giải thuật
Bước 1:
 i=1;//bắtđầutừphầntửđầutiêncủadãy
Bước 2: Sosánha[i]vớix,có2khảnăng:

a[i]=x:Tìmthấy.Dừng

a[i]!=x:SangBước3.
Bước 3:


7 5 12 41 10 32 13 9 15 3
1 2 3 4 5 6 7 8 9 10
10
10
7 5 12 41 10 32 13 9 15 3
1 2 3 4 5 6 7 8 9 10
25
11
25
25
10
11
Cài đặt
intLinearSearch2(inta[],intN,intx)
{ inti=0;
a[N]=x;//thêmphầntửxsaumảng
while(a[i]!=x)
i++;
if(i==N)
 return-1;//tìmhếtmảng
else
returni; //tìmthấyxtạivịtríi
}
Độ phức tạp tính toán cấp n: T(n)=O(n)
12
Q & A
13
Tìm kiếm nhị phân (Binary Search)
Ý tưởng


1 2 3 4 5 6 7 8 9 10
m
x
3 14 16 19 22 41 46 51 63 71
1 2 3 4 5 6 7 8 9 10
r
m
x
l
3 14 16 19 22 41 46 51 63 71
1 2 3 4 5 6 7 8 9 10
m
x
3 14 16 19 22 41 46 51 63 71
1 2 3 4 5 6 7 8 9 10
l > r: Kết thúc: Không (m
thấy
Giải thuật
Bước 1: left = 1; right = N; //tìm kiếm tất cả các phần tử
Bước 2:
mid = (left+right)/2; // lấy mốc so sánh
So sánh a[mid] với x, có 3 khả năng :

a[mid] = x: Tìm thấy. Dừng

a[mid] > x: //tìm tiếp x trong dãy con a
left
a
mid -1
right =mid - 1;

18
Q & A
19
Code minh họa
#include <iostream.h>
#include<stdlib.h>
#include<time.h>
#define MAX 1000
void TaoMang(int a[], int N);
void XuatMang(int a[], int N);
int LinearSearch(int a[], int N, int x);
20
void main()
{
srand((usigned int) time (NULL));
int a[MAX], N = 20, x, kq;
TaoMang(a, N);
XuatMang(a, N);
cout<<“Nhap gia tri can tim: “;
cin>>x;
kq=LinearSearch(a, N, x);
if(kq==-1)
cout<<“Khong co phan tu can tim”;
else
cout<<“Phan tu can tim tai vi tri: ”<<kq;
}
21
void TaoMang(int a[], int N)
{
for(int i=0; i<N; i++)

LT1_2: Xây dựng giải thuật tìm kiếm phần tử có giá trị nhỏ nhất trong dãy số:
Dùng mã tự nhiên, mã giả và lưu đồ.
25
3 4 6 6 12 16 21 34 41 80
1 2 3 4 5 6 7 8 9 10