Ktl-icon-tai-lieu

Thuật toán Tìm kiềm nhị phân

Được đăng lên bởi Thanh Thúy Đinh
Số trang: 15 trang   |   Lượt xem: 444 lần   |   Lượt tải: 0 lần
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KINH TẾ - LUẬT
UNIVERSITY OF ECONOMIC AND LAW
KHOA HỆ THỐNG THÔNG TIN
LỚP K12406

Nhóm: Cửa hàng tạp hóa
Giảng viên hướng dẫn: ThS.Trương Hoài Phan
Thứ 6, ngày 15 tháng 11 năm 2013

NỘI DUNG THUYẾT TRÌNH
1

Mở đầu
Xét bài toán

2
3

Tìm kiếm
nhị phân

4
5

6
7

Cài đặt
Ví dụ minh họa
Ví dụ thực tế
Đánh giá
Nhận xét

1

a. Danh
Danh sách
sách thành
thành viên
viên
1

Lưu Trọng Thông

2

Bùi Thị Kim Duyên

3

Vũ Thị Thanh Mai

4

Trương Thị Thảo

5

Đinh Thị Thanh Thúy

Mở đầu

1

Mở đầu

b. Đặt
Đặt vấn
vấn đề
đề
2.
○

Thuật toán
tìm kiếm

○
○
○
Tìm kiếm
Tuyến tính

Tìm kiếm
Nhị phân

Xét bài toán

2

Cho dãy số A gồm N số nguyên tăng khác nhau a1,
a2, …, aN và số nguyên k, nếu có ai = k (1 ≤ i ≤ N)
thì thông báo chỉ số i.

Dãy A gồm N số nguyên tăng khác nhau a0,a1, ..., aN-1

Input

Số nguyên k

Output

Chỉ số I mà

M ai= k hoặc không có số hạng nào của dãy A có giá trị bằng k.

a.

Ý
Ý tưởng
tưởng

Xét bài toán

2

○ Sử dụng tính chất A là dãy tăng, ta tìm cách thu hẹp nhanh
phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng được
chọn. Để làm điều đó, ta chọn số hạng aGiua ở "giữa dãy" để
so sánh với k;
○ Khi đó, chỉ xảy ra một trong 3 trường hợp sau:
+ Nếu a[Giua] = k thì Giua là chỉ số cần tìm => Kết thúc.
+ Nếu a[Giua]> k thì do A là dãy đã được sắp xếp nên việc tìm
kiếm tiếp theo chỉ xét trên dãy a1, a2,..., aGiua–1 (phạm vi tìm
kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó).
+ Nếu a[Giua]< k thì thực hiện tìm kiếm trên dãy aGiua+1,
aGiua+2,..., aN-1.
Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã
tìm thấy khoá k trong A hoặc phạm vi tìm kiếm bằng rỗng.

b.

Thuật
Thuật toán
toán

Xét bài toán

2

Cài đặt

int BinarySearch(int key)
{
int left = 0, right = n-1, mid;
while (left <= right)
{
mid = (left + right)/ 2; // lấy điểm giữa
if (a[mid] == key) // nếu tìm được
return mid;
if (a[mid] < x) // tìm đoạn bên phải mid
left = mid+1;
else
right = mid-1; // tìm đoạn bên trái mid

3

4

Ví dụ minh họa
○

a.

Đề
Đề bài
bài

Ví dụ thực tế
Bài toán kinh điển

5

b. Giải
Giải quyết
quyết bài
bài toán
toán

Ví dụ thực tế

5

○ Sắp xếp số gà theo thứ tự tăng dần (theo chiều từ dưới

lên)
○ Chia đôi tổng số gà, nếu tại điểm giữa đó tổng số chân gà
và chân chó lớn hơn 100 thì lấy nửa trên, và ngược lại lấy
nửa dưới.

Đánh giá
Có 3 trường hợp xảy ra
Trường hợp tốt nhất: so sánh 1 lần:
phần tử giữa của mảng có giá trị key

Trường hợp xấu nhất: so sánh log2 n:
không có key trong mảng
...
Nhóm: Cửa hàng tạp hóa
Giảng viên hướng dẫn: ThS.Trương Hoài Phan
Thứ 6, ngày 15 tháng 11 năm 2013
LỚP K12406
LỚP K12406
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KINH TẾ - LUẬT
U N I V E R S I T Y O F E C O N O M I C A N D L A W
KHOA HỆ THỐNG THÔNG TIN
KHOA HỆ THỐNG THÔNG TIN
Thuật toán Tìm kiềm nhị phân - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Thuật toán Tìm kiềm nhị phân - Người đăng: Thanh Thúy Đinh
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
15 Vietnamese
Thuật toán Tìm kiềm nhị phân 9 10 598