1. Tìm kiếm - một khái niệm quen thuộc trong cuộc sống

Có bao giờ bạn phải đau đầu vì để quên chiếc ví ở đâu đó trong nhà mà tìm mãi không thấy? Hay việc các bạn nữ luôn không thể nào tìm thấy bộ quần áo phù hợp để lên phố mặc dù số lượng trang phục xếp nặng trĩu trong tủ quần áo? Cuộc sống chúng ta luôn gắ...

2. Bài toán tìm kiếm trong Tin học

Cùng so sánh hai sự việc sau đây:Mục tiêu tìm kiếm trong cả hai bài toán đều đã được xác định, đó là "cục tẩy" và "số 666" (cần tìm thấy số 666 xong mới có được vị trí). Và tập "dữ liệu" của chúng ta có (hay phạm vi tìm kiếm) chính là "những đồ vật tr...

Ý tưởng

Tìm kiếm tuần tự (Sequential Search hay Linear Search) là một giải thuật đơn giản, rất dễ cài đặt. Bắt đầu từ đối tượng a1,a_1,a1​, duyệt qua tất cả các đối tượng, cho tới khi tìm thấy đối tượng có khóa mong muốn, hoặc duyệt hết toàn bộ dãy mà không tìm thấy khóa đó.Mô phỏng giải thuật C++:

Đánh giá

Mặc dù giải thuật Tìm kiếm tuần tự rất đơn giản và dễ cài đặt, tuy nhiên nhược điểm của nó nằm ở độ phức tạp. Trong trường hợp tốt nhất, giải thuật có độ phức tạp là O(1),O(1),O(1), nhưng trong trường hợp xấu nhất lên tới O(n)O(n)O(n). Vì vậy độ phức tạp tổng quát của giải thuật là O(n),O(n),O(n), chỉ phù hợp với những bài toán có kích thước không gian tìm kiếm nhỏ.

Ví dụ

Cho một dãy số aaa gồm nnn số nguyên a1,a2,...,an (1≤n≤1000)a_1, a_2,..., a_n (1 le n le 1000)a1​,a2​,...,an​ (1≤n≤1000). Hãy xác định xem số fibonacci thứ k (1≤k≤100)k (1 le k le 100)k (1≤k≤100) có xuất hiện trong dãy số hay không, nếu có thì đưa ra vị trí xuất hiện đầu tiên, ngược lại đưa ra −1-1−1.

Cách giải quyết

Trước tiên, ta dùng vòng lặp để tìm ra số fibonacci thứ k,k,k, rồi tìm kiếm tuần tự trên dãy số ban đầu để tìm ra vị trí của số fibonacci thứ kkk trong dãy.

Cài đặt

Ý tưởng

Trước tiên, không gian tìm kiếm cần được sắp xếp lại theo chiều tăng dần hoặc giảm dần của khóa tìm kiếm (mục tiêu là để tạo ra dãy có tính thứ tự). Giả sử dãy đã được sắp xếp tăng dần theo khóa, giải thuật tìm kiếm nhị phân được thực hiện như sau:Quá trình tìm kiếm sẽ thất bại nếu như đến một bước nào đó, tập tìm kiếm bị rỗng (l>r)(l > r)(l>r).Mô phỏng giải thuật C++:

Đánh giá

Trong trường hợp tốt nhất, giải thuật Tìm kiếm nhị phân cho ta độ phức tạp O(1)O(1)O(1). Còn trong trường hợp xấu nhất, do tập tìm kiếm luôn luôn được chia đôi ra, nên số thao tác chỉ mất O(log⁡2(n))O(log_2(n))O(log2​(n)). Vì thế, độ phức tạp tổng qu...

Ví dụ

Cho dãy số AAA gồm n (1≤n≤105)n (1 le n le 10^5)n (1≤n≤105) phần tử nguyên dương a1,a2,...,an (ai≤109)a_1, a_2,..., a_n (a_i le 10^9)a1​,a2​,...,an​ (ai​≤109). hãy xác định số chính phương nhỏ nhất không xuất hiện trong dãy số?

Cách giải quyết

Với bài toán này, phương pháp đếm phân phối cũng có thể được áp dụng, tuy nhiên mình sẽ trình bày phương pháp tìm kiếm nhị phân để minh họa cách áp dụng giải thuật. Đầu tiên, sắp xếp dãy số đã cho theo thứ tự tăng dần. Ta nhận thấy, do ai≤109a_i le 10^9ai​≤109 nên ai≤109.sqrt{a_i} le sqrt{10^9}.ai​​≤109​. Vậy chỉ cần duyệt qua các giá trị iii từ 000 tới max(ai)+1,sqrt{text{max}(a_i)} + 1,max(ai​)​+1, sau đó tìm kiếm nhị phân trên dãy xem có tồn tại giá trị i2i^2i2 hay không, nếu không thì đó chính là số chính phương nhỏ nhất không xuất hiện trong dãy.

Cài đặt

©️ Tác giả: Vũ Quế Lâm từ Viblo