Bài toán cụ thể của tìm kiếm nhị phân
Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một thuật toán được sử dụng rất nhiều trong lập trình lập trình: tìm kiếm nhị phân. Hãy cùng xem thuật toán này có gì thú vị nhé! Show Nội dungĐể có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:
Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:
Bài toán đặt raCho một dãy số gồm n số nguyên dươngai (n≤106, ai≤109). Cóq truy vấn(q ≤ 106), mỗi truy vấn gồm một số nguyên dươngx, nếux có trong dãy a thì in ra “YES”, còn không thì in ra “NO”. Ví dụ: _Howkteam_com.png) Lời giải ban đầuGiải thích: Trong ví dụ trên có 5 truy vấn là 3, 4, 8, 9, 1 với kết quả lần lượt là YES, NO, YES, YES, NO với ý nghĩa như đã nêu ở đề bài. Với suy nghĩ thông thường, để có thể kiểm tra được 1 phần tử có trong dãy hay không, ta sẽ duyệt qua toàn bộ dãy. Nếu như gặp một phần tử giống với giá trị đang tìm kiếm, ta sẽ in ra “YES”, còn nếu tìm cả dãy mà không thấy, ta sẽ in ra “NO”. Từ suy nghĩ trên, ta sẽ code như sau: ` includeusing namespace std; const int MaxN = 1 + 1e6; int n, a[MaxN], q; int main(){ }
`Hãy cùng đánh giá độ phức tạp của thuật toán trên. Ta nhận thấy có một vòng lặpn lần nằm trong một vòng lặpq lần nên độ phức tạp của thuật toán làO(n × q). Vậy liệu có cách nào giảm độ phức tạp của thuật toán tìm kiếm xuống không? Ý tưởngGiả sử dãy số ở trong ví dụ của chúng ta được sắp xếp không giảm. Khi đó ta có a = [2, 2, 3, 5, 7, 8, 9]. Ta cần kiểm trax = 3 liệu có thuộc dãy a hay không. Vậy thì ta sẽ làm như thế nào? Hãy xét vị trí i = 4 trong dãy a(ai = 7). Khi này, ta chia dãy làm hai phần: các số nhỏ hơn 7 (màu xanh) và các số lớn hơn hoặc bằng 7 (màu vàng). _Howkteam_com.png) Ta nhận thấy 3 nhỏ hơn 7, do đó số 3 không thể nằm trong phần màu vàng mà chỉ có thể nằm trong phần màu xanh. Do đó, khi tiếp tục tìm kiếm, ta chỉ tìm kiếm trên vùng màu xanh. Việc này giúp ta giảm bớt các bước tìm kiếm. Lời giải cải tiếnTừ ý tưởng được đưa ra ở trên, ta có thể đưa ra một lời giải như sau:
Đây chính là cơ sở của thuật toán tìm kiếm nhị phân. Để tìm hiểu chi tiết hơn, ta sẽ cùng đến với phần tiếp theo của bài học ngày hôm nay. Tổng quan về tìm kiếm nhị phânKhái niệm và ý tưởngTìm kiếm nhị phân là một thuật toán tìm kiếm giá trị xác định trên dãy đã sắp xếp. Thuật toán hoạt động bằng cách chọn phần tử trung vị (phần tử ở vị trí chính giữa). Nếu phần tử cần tìm khác phần tử trung vị ta sẽ tiếp tục xét. Nếu phần tử cần tìm kiếm nhỏ hơn phần tử trung vị, ta sẽ tiếp tục tìm kiếm trên nửa nhỏ hơn, ngược lại ta sẽ tìm kiếm trên nửa lớn hơn. Kết thúc quá trình tìm kiếm mà không có phần tử nào bằng phần tử cần tìm, ta sẽ kết luận phần tử cần tìm không có trong dãy. Code` includeusing namespace std; const int MaxN = 1 + 1e6; int n, a[MaxN], q; bool binary_search(int a[], int sz, int target){ }
int main(){ }
`Mình sẽ có một số lưu ý cho các bạn về đoạn code trên như sau:
Vậy cụ thể đoạn code trên sẽ chạy như thế nào? Hãy giả sử ta đang cần tìm kiếm phần tử x = 3 trong dãy ở ví dụ. Khi đó, quá trình tìm kiếm sẽ như sau: _Howkteam_com.png) Độ phức tạp của thuật toánTa thấy, ở mỗi bước, khoảng tìm kiếm sẽ bị giảm đi một nửa nên chi phí cho việc tìm kiếm một phần tử sẽ làO(logn). Do đó, độ phức tạp của toàn bộ chương trình trên sẽ làO(n×logn). Một số hàm tìm kiếm nhị phân trong C++Trong C++ có một số hàm áp dụng tư tưởng của tìm kiếm nhị phân nhưbinary_search,lower_bound, upper_bound. Khai báoThông thường để thêm các hàm trên vào chương trình, chúng ta sẽ thêm thư viện như sau: includeTuy nhiên, ở trong suốt khóa học này mình sẽ sử dụng header sau: includeHeader này sẽ giúp chúng ta thêm tất cả các thư viện về thuật toán mà chúng ta sẽ sử dụng trongkhóa học này. Sử dụngHàm binary_searchHàm binary_searchsẽ được sử dụng như sau: binary_search({first}, {last}, {element}); Trong đó:
Hàm binary_searchsẽ được áp dụng vào bài toán ban đầu của ta như sau: ` includeusing namespace std; const int MaxN = 1 + 1e6; int n, a[MaxN], q; int main(){ }
`Hàm lower_boundHàm lower_bound sẽ được sử dụng như sau: lower_bound({first}, {last}, {element}); Trong đó:
Mình có đoạn code minh hoạ cách dùng lower_boundnhư sau: ` includeusing namespace std; const int MaxN = 1 + 1e6; int main(){ }
`Hàm upper_boundCách sử dụng hàm upper_boundhoàn toàn tương tự hàm lower_bound, chỉ khác làupper_bound sẽ tìm phần tử đầu tiên lớn hơn phần tử element. Mình có đoạn code minh hoạ cách dùng upper_boundnhư sau: ` includeusing namespace std; const int MaxN = 1 + 1e6; int main(){ }
`Độ phức tạpTất cả các hàm mình vừa nêu ở trên đều mất độ phức tạpO(logn). Vấn đề bài sauTừ những kiến thức về tìm kiếm nhị phân, các bạn hãy thử suy nghĩ bài toán sau: Có một phân xưởng gồm n máy(n ≤ 105), máy thứ i cần chính xácai ngày(0 < ai ≤ 109) để hoàn thành 1 sản phẩm như nhau. Hãy tính thời gian ít nhất để có thể hoàn thành tối thiểuk sản phẩm (0< k≤ 109). Ví dụ _Howkteam_com.png) Để biết cách làm là gì thì hãy cùng chờ đến bài học tiếp theo nhé! Giải thích: Trong vòng 10 ngày, máy 1 làm được 3 sản phẩm, máy 2 làm được 5 sản phẩm, máy 3 làm được 1 sản phẩm, tổng cộng là 9 sản phẩm như yêu cầu đề bài. Kết luậnQua bài này chúng ta đã nắm được các kiến thức ban đầu về Tìm kiếm nhị phân Bài sau chúng ta sẽ tiếp tục tìm hiểu về Ứng dụng của tìm kiếm nhị phân Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”. Tải xuốngTài liệuNhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Tổng quan về tìm kiếm nhị phân dưới dạng file PDF trong link bên dưới. Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com Đừng quên like và share để ủng hộ Kteam và tác giả nhé! Thảo luậnNếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng. |